seat_allocation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "xzaKJISMn4Av"
   },
   "source": [
    "# 座席配置問題をアニーリングマシンで解く"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "p98gdI6sn7Z0"
   },
   "source": [
    "## 事前準備"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "AR7kB3mSR2aj"
   },
   "source": [
    "### ライブラリのインストール"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "6iFUTYGOP2HJ",
    "outputId": "102024b7-a74c-4b44-fe7f-bf153263aa37"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[K     |████████████████████████████████| 7.6 MB 9.9 MB/s \n",
      "\u001b[?25h"
     ]
    }
   ],
   "source": [
    "! pip install -q amplify numpy matplotlib"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "id": "LII5U9LCERlM"
   },
   "outputs": [],
   "source": [
    "# 必要なライブラリの読み込み\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import itertools\n",
    "from typing import List\n",
    "from IPython.display import clear_output\n",
    "\n",
    "from amplify import BinarySymbolGenerator\n",
    "from amplify.constraint import one_hot, equal_to, less_equal\n",
    "# from typing_extensions import ParamSpec\n",
    "from amplify.client import FixstarsClient, FixstarsClientParametersOutputs\n",
    "from amplify import Solver"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "TSpWmNzlR2a6"
   },
   "source": [
    "### ライセンス確認\n",
    "\n",
    "本プログラムはFixstar Amplify社が提供するSDKを利用します。利用にあたってはトークンが必要になりますので，以下のサイトより入手ください。本プログラムの実行には無料版のプランで十分です。\n",
    "\n",
    "- [Fixstar Amplify](https://amplify.fixstars.com/ja/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "id": "94Wf_F_NR2a-"
   },
   "outputs": [],
   "source": [
    "FIXSTAR_CLIENT_TOKEN = input(\"PASTE YOUR TOKEN CODE: \")\n",
    "assert FIXSTAR_CLIENT_TOKEN\n",
    "clear_output()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "pr5jEd10oCXm"
   },
   "source": [
    "## ユーティリティ関数の定義\n",
    "\n",
    "後々必要になる補助関数を用意しておきます。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "id": "dJm7is2JEYWk"
   },
   "outputs": [],
   "source": [
    "def draw_table_layout(tables, xmax=10, ymax=10, figsize=(6, 6)):\n",
    "    \"\"\"\n",
    "    テーブル配置の描画\n",
    "    \"\"\"\n",
    "    fig = plt.figure(figsize = figsize)\n",
    "    ax = fig.add_subplot(111)\n",
    "    ax.set_xlim(0, xmax=xmax)\n",
    "    ax.set_ylim(0, ymax=ymax)\n",
    "\n",
    "    for key, vals in enumerate(tables):\n",
    "        x, y = vals\n",
    "        ratio_min = y / ymax\n",
    "        ratio_max = (y+1) / ymax\n",
    "        # yは相対座標で指定する\n",
    "        ax.axvspan(x, x+1, ymin=ratio_min, ymax=ratio_max, color=\"gray\", alpha=0.4)\n",
    "        ax.text(x+0.5, y+0.5, str(key))\n",
    "    return fig, ax\n",
    "\n",
    "def calc_center_point_map(tables: dict) -> List:\n",
    "    \"\"\"\n",
    "    各テーブルの中心点取得\n",
    "    \"\"\"\n",
    "    table_ids = range(len(tables))\n",
    "    num_tables = len(tables)\n",
    "    centers = [[coord[0] + 0.5, coord[1] + 0.5] for coord in tables]\n",
    "    return centers\n",
    "\n",
    "def group_member_indexes(customer_groups):\n",
    "    \"\"\"\n",
    "    顧客のインデックスに変換する\n",
    "    \"\"\"\n",
    "    i = 0\n",
    "    indexes = []\n",
    "    for x in customer_groups:\n",
    "        indexes.append(list(range(i, i+x)))\n",
    "        i += x\n",
    "    return indexes\n",
    "\n",
    "def member_index_to_group(index, customer_groups):\n",
    "    \"\"\"\n",
    "     マトリックスインデックスから顧客グループIDを取得する\n",
    "    \"\"\"\n",
    "    num = 0\n",
    "    for i, x in enumerate(customer_groups):\n",
    "        num += x\n",
    "        if num - 1 >= index:\n",
    "            return i\n",
    "\n",
    "def group_table_indexes(table_groups):\n",
    "    \"\"\"\n",
    "    テーブルのインデックスに変換する\n",
    "    \"\"\"\n",
    "    return list(table_groups.values())\n",
    "\n",
    "\n",
    "def generate_color_map(customer_groups):\n",
    "    \"\"\"\n",
    "    顧客グループごとのカラーマップを取得する\n",
    "    \"\"\"\n",
    "    cycle = plt.rcParams['axes.prop_cycle'].by_key()['color']\n",
    "    dic = {i:cycle[i]  for i, num in enumerate(customer_groups)}\n",
    "    return dic\n",
    "\n",
    "\n",
    "def draw_solutions(solution, tables, customer_groups, xmax=10, ymax=10, figsize=(6, 6)):\n",
    "    \"\"\"\n",
    "    結果の描画\n",
    "    \"\"\"\n",
    "    fig = plt.figure(figsize = figsize)\n",
    "    ax = fig.add_subplot(111)\n",
    "    ax.set_xlim(0, xmax=xmax)\n",
    "    ax.set_ylim(0, ymax=ymax)\n",
    "\n",
    "    for key, vals in enumerate(tables):\n",
    "        x, y = vals\n",
    "        ratio_min = y / ymax\n",
    "        ratio_max = (y+1) / ymax\n",
    "        # yは相対座標で指定する\n",
    "        ax.axvspan(x, x+1, ymin=ratio_min, ymax=ratio_max, color=\"gray\", alpha=0.4)\n",
    "        ax.text(x+0.5, y+0.5, str(key))\n",
    "    \n",
    "\n",
    "    rows, cols = np.where(solution==1)\n",
    "    color_map = generate_color_map(customer_groups)\n",
    "    for i, j in zip(rows, cols):\n",
    "        group_idx =  member_index_to_group(j, customer_groups)\n",
    "        color = color_map[group_idx]\n",
    "\n",
    "        table_x, table_y = tables[i]\n",
    "        ratio_min = table_y / ymax\n",
    "        ratio_max = (table_y+1) / ymax\n",
    "        # yは相対座標で指定する\n",
    "        ax.axvspan(table_x, table_x+1, ymin=ratio_min, ymax=ratio_max, color=color)\n",
    "\n",
    "        ax.text(table_x, table_y+0.5, f\"g{group_idx}\")\n",
    "\n",
    "    return fig, ax\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "VYKNp5JlpPy4"
   },
   "source": [
    "## 問題設定\n",
    "\n",
    "複数のお客さんグループをなるべく効率的にテーブルに配置させるという問題を考えます。\n",
    "\n",
    "「効率的に」とは以下の条件を満たすことを指すこととします。\n",
    "\n",
    "- １．テーブルの座席数をなるべく埋める（４人掛けのテーブルにはなるべく４人グループを割り当てる）\n",
    "- ２．グループが同じ人はなるべく近いテーブルに座らせる\n",
    "- ３．他のグループとの距離はなるべく離す\n",
    "\n",
    "後で以上の条件を数式に落とし込んでいきます。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 413
    },
    "id": "jRxu5oXzFMy_",
    "outputId": "0b4ef442-5ad6-4ad4-e667-70d1731384fe"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "customer numbers: 19, table numbers: 21\n",
      "customer group members: [2, 3, 8, 6]\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAFpCAYAAABnHGgVAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAdZklEQVR4nO3de3RV1b328edHAsollAQIIpeRABW0aY/NmwaO1SJEBCkoVksVoXjGGQYHIF6otEAVUVt6ofagta14gSomCFREkFY0CBRsuaRiC7VYa4MKQqQxGAUsCfP9IxFojS3s21zMfD9jMNh7J2uvZ6y59pOVmbXXNuecAABhaeY7AAAg8Sh3AAgQ5Q4AAaLcASBAlDsABIhyB4AA/cdyN7NHzKzSzLYd91iWmT1nZn9p+D8zuTEBACfjRI7c50sa8i+PfUtSmXPu05LKGu4DACLCTuRNTGaWI2mFcy6v4f4OSRc65942s86S1jjneiczKADgxMU6597JOfd2w+09kjolKA8AIAHS430C55wzs088/DezYknFktS6dev/16dPn3hXCQBNSnl5+T7nXMeTWSbWct9rZp2Pm5ap/KRvdM7NlTRXkgoKCtyWLVtiXCUANE1mtvNkl4l1WuZpSWMbbo+VtCzG5wEAJMGJnApZKum3knqb2Vtm9r+SvidpkJn9RdJFDfcBABHxH6dlnHNXf8KXihKcBQCQILxDFQACRLkDQIAodwAIEOUOAAGi3AEgQJQ7AASIcgeAAFHuABAgyh0AAkS5A0CAKHcACBDlDgABotwBIECUOwAEiHIHgABR7gAQIModAAJEuQNAgCh3AAgQ5Q4AAaLcASBAlDsABIhyB4AAUe4AECDKHQACRLkDQIAodwAIEOUOAAGi3AEgQJQ7AASIcgeAAFHuABAgyh0AAkS5A0CAKHcACBDlDgABotwBIECUOwAEiHIHgABR7gAQIModAAJEuQNAgCh3AAgQ5Q4AAaLcASBAlDsABIhyB4AAUe4AECDKHQACRLkDQIAodwAIEOUOAAGi3AEgQJQ7AASIcgeAAFHuABCguMrdzG42s+1mts3MSs3s9EQFAwDELuZyN7MukiZJKnDO5UlKk3RVooIBAGIX77RMuqSWZpYuqZWk3fFHAgDEK+Zyd87tkjRb0huS3pa03zm3KlHBAACxi2daJlPSZZJyJZ0pqbWZjW7k+4rNbIuZbXnnnXdiTwoAOGHxTMtcJOlvzrl3nHOHJT0p6bx//Sbn3FznXIFzrqBjx45xrA4AcKLiKfc3JPUzs1ZmZpKKJL2SmFgAgHjEM+e+UdISSb+X9MeG55qboFwAgDikx7Owc26GpBkJygIASBDeoQoAAaLcASBAlDsABIhyB4AAUe4AECDKHQACRLkDQIAodwAIEOUOAAGi3AEgQJQ7AASIcgeAAFHuABAgyh0AAkS5A0CAKHcACBDlDgABotwBIECUOwAEiHIHgABR7gAQIModAAJEuQNAgCh3AAgQ5Q4AAaLcASBAlDsABIhyB4AAUe4AECDKHQACRLkDQIAodwAIEOUOAAGi3AEgQJQ7AASIcgeAAFHuABAgyh0AAkS5A0CAKHcACBDlDgABotwBIECUOwAEiHIHgABR7gAQIModAAJEuQNAgCh3AAgQ5Q4AAaLcASBAlDsABIhyB4AAUe4AECDKHQACRLkDQIAodwAIEOUOAAGKq9zNrJ2ZLTGzP5vZK2b234kKBgCIXXqcy8+R9Gvn3JVm1kJSqwRkAgDEKeZyN7NPSfqSpGslyTn3D0n/SEwsAEA84jlyz5X0jqR5ZvZfksol3eic++D4bzKzYknFktS9e/c4VpcYmzZtUk1Nje8YysjIUGFhoe8YkRCFMamqqlJWVpbXDFI09osojIcUjTGJwnjEKp5yT5eUL+kG59xGM5sj6VuSbjv+m5xzcyXNlaSCggIXx/oSoqamRu3atfMdQ9XV1b4jREYUxqSiokI9evTwmkGKxn4RhfGQojEmURiPWMXzB9W3JL3lnNvYcH+J6sseAOBZzOXunNsj6U0z693wUJGkPyUkFQAgLvGeLXODpMcbzpR5XdL/xB8JABCvuMrdObdVUkGCsgAAEoR3qAJAgCh3AAgQ5Q4AAaLc41BXV6dRo0bppptu8h0FkmbOnKlBgwZp5MiRH/vaggULVFBQkPTzlj8pw8KFC3XFFVdo5MiRmjNnTlIzREVj22LHjh269tprNWrUKI0ZM0bbtm1LaoY9e/Zo3Lhx+upXv6qRI0eqtLRUkrR//36NHz9el19+ucaPH6/33nsvqTl8oNzjUFpaqtzcXN8x0GD48OG67777Pvb4nj179Lvf/U5nnHGGlwxbtmzRunXrVFpaqkWLFmnMmDFJzxEFjW2Le++9V9ddd51KSko0btw43XvvvUnNkJ6erptvvlmLFy/WvHnztHjxYr3++uuaP3++CgsLtXTpUhUWFmr+/PlJzeED5R6jvXv3asOGDRoxYoTvKGiQn5+vtm3bfuzxe+65R5MmTZKZecmwZMkSjR07Vi1atJAk72+pT5XGtoWZ6YMP6q9Q8v7776tjx45JzdChQwf16dNHktS6dWvl5OSosrJSa9eu1bBhwyRJw4YN05o1a5Kaw4d4z3Nvsn70ox9p0qRJR3dURNOaNWuUnZ2ts846y1uGN954Q1u3btVPf/pTnXbaabrxxhv1mc98xlsenyZPnqyJEydqzpw5OnLkiB555JGUrXv37t3asWOH8vLyVFVVpQ4dOkiS2rdvr6qqqpTlSBWO3GPwm9/8RllZWTr77LN9R8G/cejQIc2bN0/XX3+91xy1tbXav3+/5s+fr0mTJmnq1KlyzvtllrxYsmSJbrnlFj3zzDO65ZZbdNddd6VkvQcOHNCUKVM0efJktWnT5p++ZmYp+a0u1Sj3GLz88stat26dhg8frunTp2vz5s267bbb/vOCSKm33npLu3fv1tVXX63hw4ersrJS11xzjfbt25fSHJ06ddLAgQNlZsrLy5OZndIXpIrHihUrNHDgQEnSRRddpO3btyd9nbW1tZoyZYqGDBlydN1ZWVlH94N9+/YpMzMz6TlSjXKPwcSJE7Vy5UotX75c3/nOd/SFL3whZUcgOHG9evXSc889p+XLl2v58uXKzs7W448/fvTX8VTp37+/tmzZIknauXOnamtrI3HVRR86duyo8vJySdLmzZvVrVu3pK7POac777xTubm5Gj169NHH+/fvrxUrVkiq/4HTv3//pObwgTl3BGPatGkqLy9XdXW1hg4dquLi4pT/wbuxDJdddpnuvPNOjRw5Us2bN9cdd9wR5DTAv2psW3z729/W7NmzVVdXpxYtWmj69OlJzfDyyy9r5cqV6tWrl0aNGiVJGj9+vMaOHaupU6dq2bJl6ty5s2bNmpXUHD5YKuf+CgoK3EdHML6UlZVF4qipurpaRUVFvmNEQhTGZOvWrTr33HO9ZpCisV9EYTykaIxJFMZDksys3Dl3UtfxYloGAAJEuQNAgCh3AAgQ5Q4AAaLcASBAlDsABIhyB4AAUe4AECDKHQACRLkDQIAodwAIEOUOAAGi3AEgQJQ7AASIcgeAADW5D+uoqqpSRUWF7xgf+1T4piwKY1JdXa2tW7d6zSBFY7+IwnhI0RiTKIxHrJpcuWdlZalHjx6+YzTZz9BsTBTGJAofDCFFY7+IwnhI0RiTKIxHrJiWAYAAUe4AECDKHQACRLkDQIAodwAIEOUOAAGi3AEgQE3uPPdE+fDDD3Xdddfp8OHDqqurU1FRkcaNG+c7VpM2c+ZMrV+/XpmZmVq0aJEk6Wc/+5nWrl2rZs2aKTMzU3fccYc6duyY0gwPPPCAnnrqKWVmZkqSxo8fr/PPPz9pGaKisW0xdepU7dy5U5JUU1OjjIwMlZSUpDzHq6++qlmzZunAgQM688wzddddd6lNmzZJzZFqHLnHqEWLFvr5z3+u0tJSlZSU6MUXX9Qf//hH37GatOHDh+u+++77p8fGjBmjhQsXqqSkRBdccIEefPDBlGeQpFGjRqmkpEQlJSVNotilxrfFrFmzjm6HgQMHasCAAV5y3H333Zo4caKeeOIJXXjhhXrssceSniPVKPcYmZlatWolSaqtrVVtba3MzHOqpi0/P/9jbxc//mjs4MGDSR+jxjI0Vf9uWzjn9Pzzz2vw4MFecuzcuVP5+fmSpL59+2r16tVJz5FqlHsc6urqNGrUKA0aNEh9+/ZVXl6e70hoxP33368vf/nL+tWvfqXrr7/eS4ZFixbpqquu0syZM/Xee+95yRAlL730krKystS9e3cv6+/Zs6fWrl0rSXr++ee1d+9eLzmSiXKPQ1pamkpKSrRy5Upt375dr732mu9IaMSECRP0zDPP6JJLLjk655pKV155pZ566imVlJSoQ4cO+vGPf5zyDFHz7LPPpuSo/ZPcfvvtWrx4sUaPHq0DBw6oefPm3rIkC+WeABkZGSooKNBvf/tb31Hwb1xyySUqKytL+Xrbt2+vtLQ0NWvWTJdffrm2b9+e8gxRUltbqxdeeEGDBg3yliEnJ0f333+/FixYoMGDB6tLly7esiQL5R6jd999VzU1NZKkQ4cOaePGjcrJyfEbCh/zxhtvHL29Zs0aL2O0b9++o7dfeOEF9ezZM+UZomTTpk3KyclRp06dvGWoqqqSJB05ckQPP/ywrrjiCm9ZkoVTIWO0b98+zZgxQ0eOHNGRI0c0aNAgXXDBBb5jNWnTpk1TeXm5qqurNXToUBUXF2vDhg3auXOnmjVrps6dO2vq1Kkpz1BeXq5XX31VZqbOnTtr+vTpSc0QFY1tixEjRmjVqlW6+OKLveY4ePCgFi9eLEkaMGCALr300pTlSRVzzqVsZQUFBW7Lli0pW19jysrK1K5dO68ZpPrrRBcVFfmOEQlRGJMoXDtcisZ+EYXxkKIxJlEYD0kys3LnXMHJLMO0DAAEiHIHgABR7gAQIModAAJEuQNAgCh3AAgQ5Q4AAaLcASBAlDsABIhyB4AAUe4AEKC4y93M0szsJTNbkYhAAID4JeLI/UZJryTgeQAACRJXuZtZV0lflvRQYuIAABIh3uu5/5+kKZIyPukbzKxYUrEkb5+XeLyqqipVVFT4jsGHKB8nIyND1dXVXjO0bdvWewapflv4FoXxkKIxJlEYj1jFXO5mNkxSpXOu3Mwu/KTvc87NlTRXqr+ee6zrS5SsrCz16NHDdwzvO22UFBYW+o6A4zAeYYhnWuaLki41swpJCyUNNLMFCUkFAIhLzOXunJvqnOvqnMuRdJWk1c650QlLBgCIGee5A0CAEvIB2c65NZLWJOK5AADx48gdAAJEuQNAgCh3AAhQQubcm6I9e/ZoxowZqqqqkpnp8ssv19VXX+07FgBIotxjlp6erptvvll9+vTRBx98oDFjxqhv376ReIMUADAtE6MOHTqoT58+kqTWrVsrJydHlZWVnlMBQD3KPQF2796tHTt2KC8vz3cUAJBEucftwIEDmjJliiZPnqw2bdr4jgMAkij3uNTW1mrKlCkaMmSIBg4c6DsOABxFucfIOac777xTubm5Gj2aS+oAiBbOlonRyy+/rJUrV6pXr14aNWqUJGn8+PE6//zzPScDAMo9Zueee662bNniOwYANIppGQAIEOUOAAGi3AEgQJQ7AASIcgeAAFHuABAgyh0AAkS5A0CAKHcACBDlDgABotwBIECUOwAEiHIHgABR7gAQIModAALU5K7nnpGRoerqat8xlJGR4TsCgIA1uXIvLCz0HQEAko5pGQAIEOUOAAGi3AEgQJQ7AASIcgeAAFHuABAgyh0AAkS5A0CAKHcACBDlDgABotwBIECUOwAEiHIHgABR7gAQIModAAJEuQNAgCh3AAgQ5Q4AAaLcASBAlDsABIhyB4AAUe4AECDKHQACRLkDQIAodwAIEOUOAAGi3AEgQDGXu5l1M7MXzOxPZrbdzG5MZDAAQOzS41i2VtJk59zvzSxDUrmZPeec+1OCsgEAYhTzkbtz7m3n3O8bbtdIekVSl0QFAwDELiFz7maWI+nzkjYm4vkAAPGJZ1pGkmRmbST9UtJNzrn3Gvl6saRiSTrjjDNUVlYW7yrjUlVVpaysLK8ZJCkjI0OFhYW+Y0TCpk2bVFNT4zVDVMYjCtsiKq+RKOSIyn4Ri7jK3cyaq77YH3fOPdnY9zjn5kqaK0m9e/d27dq1i2eVcauoqFCPHj28ZpCk6upq3xEio6amRr73i6iMRxS2RVReI1HIEZX9IhbxnC1jkh6W9Ipz7p7ERQIAxCueOfcvShojaaCZbW34NzRBuQAAcYh5WsY5t16SJTALACBBeIcqAASIcgeAAFHuABCguM9z9+HFF1/U7NmzdeTIEY0YMULXXnttyjPMnDlT69evV2ZmphYtWpTy9ePjampqdNddd+mvf/2rzEy33367Pve5z/mO5cXjjz+uZcuWSZJ69eqlGTNm6LTTTktphsZeI/v379fUqVP19ttvq3Pnzvre976ntm3bpjzHnDlztG7dOjVv3lxdu3bVjBkzlJGRkdQcqXbKHbnX1dXp+9//vu69914tXrxYzz77rF5//fWU5xg+fLjuu+++lK8Xn2z27Nk677zz9Mtf/lKlpaXKzc31HcmLyspKPfHEE3r00Ue1aNEiHTlyRKtWrUp5jsZeI/Pnz1dhYaGWLl2qwsJCzZ8/30uOvn376oknntDChQvVvXt3zZs3L+k5Uu2UK/ft27erW7du6tq1q5o3b66LL75Ya9euTXmO/Pz8pB9x4MS9//77eumll3TZZZdJkpo3bx7ckdjJqKur04cffqja2lodOnRIHTt2THmGxl4ja9eu1bBhwyRJw4YN05o1a7zk6Nevn9LT6ycuPvvZz6qysjLpOVLtlJuWqaysVKdOnY7ez87O1rZt2zwmQhTs2rVL7dq108yZM/Xqq6/q7LPP1je+8Q21bNnSd7SUy87O1ujRozVs2DCddtpp6tevn/r16+c7lqT6Swp06NBBktS+fXtVVVV5TiQ9/fTTGjRokO8YCXfKHbkDjamrq9OOHTt05ZVXqqSkRC1btkzJr/xR9N5772nt2rV6+umn9etf/1oHDx7UypUrfcf6GDNT/Rvd/Xn44YeVlpamSy65xGuOZDjlyj07O1t79+49er+yslLZ2dkeEyEKsrOzlZ2drby8PElSUVGR/vznP3tO5cemTZt05plnKjMzU+np6RowYID+8Ic/+I4lScrKytK+ffskSfv27VNmZqa3LMuXL9f69et19913e/8hkwynXLmfc845evPNN7Vr1y4dPnxYq1at0pe+9CXfseBZhw4d1KlTJ1VUVEiqLzjfF53y5YwzztC2bdt06NAhOee0efNm5eTk+I4lSerfv79WrFghSVqxYoX69+/vJceLL76oRx99VPfcc49OP/10LxmS7ZSbc09PT9ett96qG264QXV1dbr00kvVs2fPlOeYNm2aysvLVV1draFDh6q4uFgjRoxIeQ4cc+utt+q2227T4cOH1aVLF82YMcN3JC/y8vJUVFSka665Rmlpaerdu7e+8pWvpDxHY6+RsWPHaurUqVq2bJk6d+6sWbNmeckxf/58HT58WBMmTJBUv82mTZuW9CypZM65lK2sd+/erqSkJGXra8zWrVt17rnnes0g1V9KtKioyHeMSCgrK/N+mduojEcUtkVUXiNRyBGV/cLMyp1zBSezzCk3LQMA+M8odwAIEOUOAAGi3AEgQJQ7AASIcgeAAFHuABAgyh0AAkS5A0CAKHcACBDlDgABotwBIECUOwAEiHIHgABR7gAQoJR+WEezZs1UXV2dylV+TNu2bb1nkKSMjAzfESKjqqrq6Cco+dK2bVuv6/9IFLZFdXW1tm7d6jVDVHJEZb+IRUrLvXXr1pG48D2iJSsry/tH4kXhB74UjW0RhQ/JiEqOqOwXsWBaBgACRLkDQIAodwAIEOUOAAGi3AEgQJQ7AASIcgeAAKX0PHcgmYYPH65WrVopLS1NaWlpeuyxx3xH8qKiokLTpk07en/Xrl0aN26cRo0alfIspaWlWrp0qSRpxIgRXjLMnDlT69evV2ZmphYtWiRJev755zV37lz97W9/0y9+8Qudc845Kc+VbJQ7gvLAAw+oXbt2vmN4lZOTo5KSEklSXV2dhg4dqgEDBqQ8x2uvvaalS5fq0UcfVXp6uiZNmqQLLrhA3bp1S2mO4cOH62tf+5puv/32o4/17NlTP/jBD/Td7343pVlSiWkZIGCbN29Wly5d1Llz55Svu6KiQnl5eTr99NOVnp6u/Px8rV69OuU58vPzP3YZgdzcXOXk5KQ8SypR7giGmWnChAkaPXq0nnzySd9xIuHZZ5/V4MGDvay7Z8+e2rp1q6qrq3Xo0CFt2LBBe/fu9ZKlKWJaBsF46KGHlJ2draqqKk2YMEE5OTnKz8/3Hcubw4cPa926dZo4caKX9efm5urrX/+6Jk6cqJYtW+qss85SWlqalyxNEUfuCEZ2drak+otvXXjhhdq+fbvnRH5t2LBBffr0Ufv27b1lGDFihBYsWKAHH3xQbdu2Vffu3b1laWoodwTh4MGD+uCDD47e3rhxo3r27Ok5lV8+p2Q+UlVVJUnas2ePVq9erSFDhnjN05QwLYMg/P3vf9ett94qqf4MkcGDB+u8887znMqfgwcPatOmTZo+fbrXHFOmTNH+/fuVnp6ub37zm14+x2DatGkqLy9XdXW1hg4dquLiYn3qU5/SD3/4Q7377ru66aabdNZZZ+knP/lJyrMlE+WOIHTt2lWlpaW+Y0RGy5YtVVZW5juGHnroId8RPvF0Rx+nh6YS0zIAECDKHQACRLkDQIAodwAIEOUOAAGi3AEgQJQ7AASIcgeAAFHuABAgyh0AAkS5A0CA4ip3MxtiZjvM7DUz+1aiQgEA4hNzuZtZmqT7JV0i6RxJV5tZeJ8yCwCnoHiO3Aslveace9059w9JCyVdlphYAIB4xFPuXSS9edz9txoeAwB4lvTruZtZsaTihrsfmtm2ZK/zFNFB0j7fISKCbXEM2+IYtsUxvU92gXjKfZekbsfd79rw2D9xzs2VNFeSzGyLc64gjnUGg21xDNviGLbFMWyLY8xsy8kuE8+0zGZJnzazXDNrIekqSU/H8XwAgASJ+cjdOVdrZhMlPSspTdIjzrmm/XHzABARcc25O+dWSlp5EovMjWd9gWFbHMO2OIZtcQzb4piT3hbmnEtGEACAR1x+AAAClJJy5zIF9cysm5m9YGZ/MrPtZnaj70y+mVmamb1kZit8Z/HJzNqZ2RIz+7OZvWJm/+07ky9mdnPD62ObmZWa2em+M6WKmT1iZpXHnzJuZllm9pyZ/aXh/8wTea6klzuXKfgntZImO+fOkdRP0oQmvC0+cqOkV3yHiIA5kn7tnOsj6b/URLeJmXWRNElSgXMuT/Una1zlN1VKzZc05F8e+5akMufcpyWVNdz/j1Jx5M5lCho45952zv2+4XaN6l/ATfZdvWbWVdKXJT3kO4tPZvYpSV+S9LAkOef+4Zyr9pvKq3RJLc0sXVIrSbs950kZ59w6SVX/8vBlkn7RcPsXkkacyHOloty5TEEjzCxH0uclbfSbxKv/kzRF0hHfQTzLlfSOpHkNU1QPmVlr36F8cM7tkjRb0huS3pa03zm3ym8q7zo5595uuL1HUqcTWYg/qHpgZm0k/VLSTc6593zn8cHMhkmqdM6V+84SAemS8iX9zDn3eUkf6AR/9Q5Nw3zyZar/gXempNZmNtpvquhw9ac3ntApjqko9xO6TEFTYWbNVV/sjzvnnvSdx6MvSrrUzCpUP1U30MwW+I3kzVuS3nLOffRb3BLVl31TdJGkvznn3nHOHZb0pKTzPGfyba+ZdZakhv8rT2ShVJQ7lyloYGam+nnVV5xz9/jO45NzbqpzrqtzLkf1+8Rq51yTPEJzzu2R9KaZfXRxqCJJf/IYyac3JPUzs1YNr5ciNdE/Lh/naUljG26PlbTsRBZK+lUhuUzBP/mipDGS/mhmWxsem9bwTl80bTdIerzhAOh1Sf/jOY8XzrmNZrZE0u9Vf3bZS2pC71Q1s1JJF0rqYGZvSZoh6XuSFpnZ/0raKWnkCT0X71AFgPDwB1UACBDlDgABotwBIECUOwAEiHIHgABR7gAQIModAAJEuQNAgP4/TeReJbQBTK8AAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x432 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# 各テーブルの位置を指定します。テーブルの左下の座標を指定しています。\n",
    "tables = [ [0,1], [1,1], [1,3], [1,4], [1,5], [4,0], [4,1], [6,0], [6,1],  [7,0],  [7,1],  [8,0],  [8,1],  [4,4],  [4,5],  [5,4],  [5,5],  [7,4],  [7,5],  [8,4],  [8,5]]\n",
    "\n",
    "# テーブルのグループを指定します。\n",
    "table_groups = {\n",
    "    \"A\": [0, 1],\n",
    "    \"B\": [2, 3, 4],\n",
    "    \"C\": [5, 6],\n",
    "    \"D\": [7, 8, 9, 10, 11, 12],\n",
    "    \"E\": [13, 14, 15, 16],\n",
    "    \"F\": [17, 18, 19, 20]\n",
    "}\n",
    "\n",
    "# お客さんのグループを指定します。数値は何人のグループかを表しています。\n",
    "customer_groups = [\n",
    "    (2),\n",
    "    (3),\n",
    "    (8),\n",
    "    (6)\n",
    "]\n",
    "\n",
    "Nc = sum([x for x in customer_groups])\n",
    "Nt = len(tables)\n",
    "print(f\"customer numbers: {Nc}, table numbers: {Nt}\")\n",
    "print(f\"customer group members: {customer_groups}\")\n",
    "\n",
    "fig, ax = draw_table_layout(tables)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "lRkD8L2IpTms"
   },
   "source": [
    "## イジングモデル設計\n",
    "\n",
    "イジングモデルを設計するために以下を実施します。\n",
    "\n",
    "- 決定変数の定義\n",
    "- 制約条件の定義\n",
    "- 目的関数の定義"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "G5W8LmEObFDq"
   },
   "source": [
    "### 決定変数\n",
    "\n",
    "イジングモデルで扱える変数を設定します。ここでは，（各テーブルの数）×（人の数）のマトリックスqを用意し，i番目のテーブルにj番目の人が座れば $q_{ij}=1$，座らなければ $q_{ij}=0$ と定義します。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "id": "9zrJC2xTMvCs"
   },
   "outputs": [],
   "source": [
    "# 決定変数を (N_table x N_customers) の配列の形式で定義\n",
    "gen = BinarySymbolGenerator()\n",
    "q = gen.array(Nt, Nc)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "RPfWR4NMqJnI"
   },
   "source": [
    "### 制約条件\n",
    "\n",
    "実現可能な解を出すため，以下２つの制約条件を設定します。\n",
    "\n",
    "- 制約１：一人は必ず１つのテーブルを割り当てる\n",
    "- 制約２：一つのテーブルには一人以下しか割り当てない\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "fSNY04BQ6KQ5"
   },
   "source": [
    "$N_c$を人の総数とすると，制約条件１は以下のように表せます。\n",
    "\n",
    "$$\n",
    "\\sum_{i=0}^{N_t - 1}q_{i, j} = 1\n",
    "\\quad\n",
    "\\text{for  }  \\ j \\in \\{0, \\cdots, N_c - 1\\}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "id": "502t_yGfWCUz"
   },
   "outputs": [],
   "source": [
    "# 一人は一つのテーブル\n",
    "table_constraints = [one_hot(q[:, j]) for j in range(Nc)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "40Z8a0Pa7YlW"
   },
   "source": [
    "$N_t$をテーブルの総数とすると，制約条件2は以下のように表せます。\n",
    "\n",
    "$$\n",
    "\\sum_{j=0}^{N_c - 1} q_{i, j}< 1 \\quad \\text{for  }  \\ i \\in \\{0, \\cdots, N_t - 1\\}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {
    "id": "4C4TEAayWxv8"
   },
   "outputs": [],
   "source": [
    "# 一つのテーブルには一人\n",
    "overlap_constraints = [less_equal(q[i, :], 1) for i in range(Nt)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "6MdlTMJwqNZi"
   },
   "source": [
    "### 目的関数\n",
    "\n",
    "以降では問題設定の箇所でも示した，「効率的な配置」について数式に落とし込んでいきます。\n",
    "\n",
    "再掲しますが，「効率的な配置」とは以下のように定義しました。\n",
    "\n",
    "- １．テーブルの座席数をなるべく埋める（４人掛けのテーブルにはなるべく４人グループを割り当てる）\n",
    "- ２．グループが同じ人はなるべく近いテーブルに座らせる\n",
    "- ３．他のグループとの距離はなるべく離す"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "mcde4rOEfHR_"
   },
   "source": [
    "#### １．テーブルをなるべく埋める"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "IDY8fyIW8Xgm"
   },
   "source": [
    "各テーブルは島を作っています。（４人席，６人席など）各島を${i_g}$とし，島に配置されたテーブルの数を$N_{i_g}$とします。この時，テーブルになるべく詰めるという条件は以下のように表せます。\n",
    "\n",
    "$$\n",
    "\\min ( \\sum_{i_g} \\lbrace \\lbrack - \\sum_{i \\in i_g} \\sum_{j} q_{i, j} + N_{i_g}  \\rbrack \\cdot \\sum_{i \\in i_g} \\sum_{j} q_{i, j} \\rbrace) \\quad \n",
    "$$\n",
    "\n",
    "ここで，minの中で$\\sum_{i \\in i_g} \\sum_{j} q_{i, j}$をかけているのは，ひとが一人も配置されなかった時のペナルティを０にするためです。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "id": "SSng5RsYpxLO"
   },
   "outputs": [],
   "source": [
    "# テーブルにはなるべく詰める\n",
    "g_table_indexes = group_table_indexes(table_groups)\n",
    "table_functions = []\n",
    "for idxs in g_table_indexes:\n",
    "    capacity = len(idxs)\n",
    "    occupy = sum([q[i, j] for j in range(Nc) for i in idxs])\n",
    "    table_functions.append((-occupy + capacity) * occupy)\n",
    "g1 = sum(table_functions)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "e1MUDyhmgrjk"
   },
   "source": [
    "#### ２．グループが同じ人はなるべく近いテーブルに座らせる"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "h4PqxfwXONEM"
   },
   "source": [
    "\n",
    "言い換えると，同じグループの人の位置がなるべく近くなればよいということになります。方針としては以下です。\n",
    "\n",
    "- グループごとに割り当てられたテーブルの平均位置座標を算出する。\n",
    "- 各座標軸それぞれについて，グループ内の位置の分散を計算する\n",
    "- 各グループごとの分散の和が最小になるようにする\n",
    "\n",
    "$$\n",
    "min \\lbrace \\sum_{j_g} (\\sum_{j \\in j_g} q_{i, j} \\cdot x_{center}^{(j)}  - avg_x^{(j_g)}) ^ 2  / n_c^{(j_g)} \\rbrace \\\\\n",
    "min \\lbrace \\sum_{j_g} (\\sum_{j \\in j_g} q_{i, j} \\cdot y_{center}^{(j)}  - avg_y^{(j_g)}) ^ 2  / n_c^{(j_g)} \\rbrace \\\\\n",
    "$$\n",
    "\n",
    "ここで，各変数は以下を意味することとします。\n",
    "\n",
    "\n",
    "- $(x_{center}^{(j)}, y_{center}^{(j)})$：各人が割り当てられたテーブルの中心位置\n",
    "- $j_g$：人のグループ\n",
    "- $(avg_{x}^{(j_g)}, avg_{y}^{(j_g)})$：各グループごとの平均位置座標\n",
    "- $n_c^{(j_g)}$：各グループに含まれる人の数\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "id": "Fn8p_otmbHnN"
   },
   "outputs": [],
   "source": [
    "# グループ内のお互いの距離がなるべく近づくようにする\n",
    "# グループ内の分散最小化\n",
    "\n",
    "g_member_indexes = group_member_indexes(customer_groups)\n",
    "table_indexes = range(len(tables))\n",
    "# abs_dist_map = calc_abs_distance_map(tables)\n",
    "center_points = calc_center_point_map(tables)\n",
    "\n",
    "ux_functions = []\n",
    "group_avg_coords = []\n",
    "for member_indexes in g_member_indexes:\n",
    "    n_c = len(member_indexes)\n",
    "    # 原点からのグループ平均座標\n",
    "    # avg = sum([q[i, j] * abs_dist_map[i] for i in table_indexes for j in member_indexes]) / n_c\n",
    "\n",
    "    avg_coord_x = sum([q[i, j] * center_points[i][0] for i in table_indexes for j in member_indexes]) / n_c\n",
    "    avg_coord_y = sum([q[i, j] * center_points[i][1] for i in table_indexes for j in member_indexes]) / n_c\n",
    "    group_avg_coords.append((avg_coord_x, avg_coord_y))\n",
    "\n",
    "    # グループ内距離分散\n",
    "    var_x = sum([(sum([q[i, j] * center_points[i][0] for i in table_indexes]) - avg_coord_x) ** 2 for j in member_indexes]) / n_c\n",
    "    var_y = sum([(sum([q[i, j] * center_points[i][1] for i in table_indexes]) - avg_coord_y) ** 2 for j in member_indexes]) / n_c\n",
    "    ux_functions.append(var_x)\n",
    "    ux_functions.append(var_y)\n",
    "\n",
    "\n",
    "g2 = sum(ux_functions) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "LA7JOMRcpBbr"
   },
   "source": [
    "#### ３．他のグループとの距離はなるべく離す\n",
    "\n",
    "２と同様に考え，グループごとの平均位置の分散が最大になるようにします。\n",
    "\n",
    "$$\n",
    "\\max( \\sum_{j_g} \\lbrace (avg_{x}^{(j_g)} - \\text{avg}_x) ^ 2 \\rbrace ) / N_g \\\\ \n",
    "\\max( \\sum_{j_g} \\lbrace (avg_{y}^{(j_g)} - \\text{avg}_y) ^ 2 \\rbrace ) / N_g \n",
    "$$\n",
    "\n",
    "ここで，\n",
    "\n",
    "- ${N_g}$：グループの数\n",
    "- $(avg_{x}, avg_{y})$：グループ単位の平均位置座標\n",
    "\n",
    "また実装上，目的関数は最小値を求めるようにしたいので，最後にマイナスをつけています。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {
    "id": "vohZPQpKo00K"
   },
   "outputs": [],
   "source": [
    "# グループ間の距離分散を最大にする\n",
    "group_num= len(group_avg_coords)\n",
    "group_global_avg_x = sum([coord[0] for coord in group_avg_coords]) / group_num\n",
    "group_global_avg_y = sum([coord[1] for coord in group_avg_coords]) / group_num\n",
    "\n",
    "group_vars_x = sum([(group_avg_coords[i][0] - group_global_avg_x)**2 for i in range(group_num)]) / group_num\n",
    "group_vars_y = sum([(group_avg_coords[i][1] - group_global_avg_y)**2 for i in range(group_num)]) / group_num\n",
    "\n",
    "g3 = -(group_vars_x + group_vars_y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "9ygC8hK6qVVZ"
   },
   "source": [
    "## 求解\n",
    "\n",
    "前節で設定した制約条件と目的関数をまとめて問題を解きます。\n",
    "また，各目的関数には重要度やオーダーに応じて重みを付けます。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {
    "id": "GwlPHNzcXzuv"
   },
   "outputs": [],
   "source": [
    "# 制約条件と目的関数をまとめる\n",
    "f = 0.1 * g1 + g2 + 0.01 * g3 + sum(table_constraints) + sum(overlap_constraints)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "ILJGyENhpmYY",
    "outputId": "d46df5d6-6eb6-4c48-f627-96fb6530f8ca"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of solutions: 84\n"
     ]
    }
   ],
   "source": [
    "# クライアントの設定\n",
    "client = FixstarsClient()\n",
    "client.parameters.timeout = 1000  # タイムアウト1秒\n",
    "client.token = FIXSTAR_CLIENT_TOKEN\n",
    "client.parameters.outputs.duplicate = True  # 同じエネルギー値の解を列挙するオプション（解が複数個あるため）\n",
    "\n",
    "# ソルバの設定と結果の取得\n",
    "solver = Solver(client)\n",
    "\n",
    "result = solver.solve(f)\n",
    "print(f\"Number of solutions: {len(result)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "wq85zc6Jqful"
   },
   "source": [
    "## 結果の確認\n",
    "\n",
    "### 配置の描画\n",
    "\n",
    "求めた結果を描画してみます。同じグループの人を同じ色で塗分けています。適切に配置できていることが確認できます。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 413
    },
    "id": "AQ4sdKNjuGXD",
    "outputId": "124fdf66-40d3-4dee-e707-b6611759789c"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(<Figure size 432x432 with 1 Axes>,\n",
       " <matplotlib.axes._subplots.AxesSubplot at 0x7fefd6c02510>)"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAFpCAYAAABnHGgVAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO3deXRb5Z3/8ffXkmzLexzHS5xAVpLQBCi4BQK/Fkj3QmmB0o0p3Sbtb9oOXegcOp2WMEyXmS6/rjATaAunLG3ZSqCUlkkG2jJlCVspJIQE0qxObCe2JW/ant8fNgmhcWJZsnTz+PM6h4MsX937ySPp46tHV1fmnENERPxSUuwAIiKSfyp3EREPqdxFRDykchcR8ZDKXUTEQyp3EREPHbbczewnZrbbzP7ysuvqzew+M3t+5P9TJjamiIhkYyx77tcBb3nFdZcBq51z84HVIz+LiEhA2Fg+xGRms4C7nXOLR35+DjjDObfTzFqA+51zCyYyqIiIjN1459ybnHM7Ry63A015yiMiInkQznUFzjlnZqPu/pvZcmA5QGVl5UkLFy7MdZMiIpPKY4891umcm5bNbcZb7rvMrOVl0zK7R1vQObcSWAnQ1tbm1q5dO85NiohMTmb212xvM95pmVXAxSOXLwbuHOd6RERkAozlUMibgT8BC8xsm5l9FPgG8EYzex54w8jPIiISEIedlnHOvW+UXy3LcxYREckTfUJVRMRDKncREQ+p3EVEPKRyFxHxkMpdRMRDKncREQ+p3EVEPKRyFxHxkMpdRMRDKncREQ+p3EVEPKRyFxHxkMpdRMRDKncREQ+p3EVEPKRyFxHxkMpdRMRDKncREQ+p3EVEPKRyFxHxkMpdRMRDKncREQ+p3EVEPKRyFxHxkMpdRMRDKncREQ+p3EVEPKRyFxHxkMpdRMRDKncREQ+p3EVEPKRyFxHxkMpdRMRDKncREQ+p3EVEPKRyFxHxkMpdRMRDKncREQ+p3EVEPKRyFxHxkMpdRMRDKncREQ+p3EVEPKRyFxHxkMpdRMRDKncREQ+p3EVEPKRyFxHxkMpdRMRDKncREQ+p3EVEPKRyFxHxkMpdRMRDKncREQ+p3EVEPKRyFxHxUE7lbmafNbNnzOwvZnazmZXnK5iIiIzfuMvdzFqBfwTanHOLgRDw3nwFExGR8ct1WiYMRM0sDFQAO3KPJCIiuRp3uTvntgPfArYAO4Ee59zv8hVMRETGL5dpmSnAucBsYDpQaWYXHWS55Wa21szWdnR0jD+piIiMWS7TMm8AXnTOdTjnksDtwNJXLuScW+mca3POtU2bNi2HzYmIyFjlUu5bgFPMrMLMDFgGrMtPLBERyUUuc+4PA7cCjwNPj6xrZZ5yiYhIDsK53Ng5dzlweZ6yiIhInugTqiIiHlK5i4h4SOUuIuIhlbuIiIdU7iIiHlK5i4h4SOUuIuIhlbuIiIdU7iIiHlK5i4h4SOUuIuIhlbuIiIdU7iIiHlK5i4h4SOUuIuIhlbuIiIdU7iIiHlK5i4h4SOUuIuIhlbuIiIdU7iIiHlK5i4h4SOUuIuIhlbuIiIdU7iIiHlK5i4h4SOUuIuIhlbuIiIdU7iIiHlK5i4h4SOUuIuIhlbuIiIdU7iIiHlK5i4h4SOUuIuIhlbuIiIdU7iIiHlK5i4h4SOUuIuIhlbuIiIdU7iIiHlK5i4h4SOUuIuIhlbuIiIdU7iIiHlK5i4h4SOUuIuIhlbuIiIdU7iIiHlK5i4h4SOUuIuIhlbuIiIdU7iIiHlK5i4h4SOUuIuIhlbuIiIdU7iIiHsqp3M2szsxuNbP1ZrbOzE7NVzARERm/cI63/x5wr3PuAjMrBSrykElERHI07nI3s1rgdcCHAJxzCSCRn1giIpKLXPbcZwMdwE/N7HjgMeAS51zfyxcys+XAcoCjjjoqh83lR+JrsyhN7C12DBKlUyj9583FjhEIp91wGr3p3mLHCISaUA0PXvRgUTPo/tgvCPfHeOUy5x4GTgSuds69GugDLnvlQs65lc65Nudc27Rp03LYXH4EodghODmCQEWyXxDGIggZguJIHotcyn0bsM059/DIz7cyXPYiIlJk4y5351w7sNXMFoxctQx4Ni+pREQkJ7keLfNp4MaRI2VeAD6ceyQREclVTuXunHsSaMtTFhERyRN9QlVExEMqdxERD6ncRUQ8lOsbql655ZkkKx4YYl1Hhkf+vpK26aFDLp/OONqu6aO1uoS7368zL+Rb+8/b6X2yFwsbpY2lzPjoDEKVo98n2368jdiTMcI1YeZ/df4Bv+v8TSftv2hn4Q8WEq7O7mGfTY7RMnTd10XX6i6sxKg+vprm9zRnlSEoch2Lgb8OsOP6HbikgxBM/+B0KuZk99zJJkOiK8H2a7aT6k0BMOWMKTS8qYFUPMXWq7eS7EwSaYhw1D8cdcjH1pFI5f4yixtLuP3CKB+/e3BMy3/v4QSLGkroHZrgYJNU5eJKmt7dhIWM9l+20/HrDpovHL0Up5w+hanLprLtmm0HXJ/oShB/Jk5kamTCcxwsQ3xdnN4nepl35TxKIiX7iuZIlOtYtP+yncZ3NlJ9XDWxp2K0/6KdOV+cM2EZLGQ0v7eZ6Kwo6YE0m1ZsoupVVXT/sZuqRVVMO3saHXd3HPaxdSSatOV+5QND3PB0kmkVxsxa46SWEJcuLRvz7bf1Zvj18ym+9H/K+M6fdEqdXO2+czfdf+omXB0mUh8hOitKw1sb9v2+Ym4FPY/2HHIdlQsqSXT87X3RfnM7TRc2seV7WyY8x8Ey7Fmzh2lvn0ZJZHgWNFxzZDztJmIszIzMQAaA9ECayJRD/8HNNUOkLkKkbngboWiIsullpPam6H2il9mXzQag7vQ6XvzGiyp3Hzy6Pc1t65I89YlKkmk4cWUfJ7Vk95LsM/cO8h9vKCeWcBOUcvLof6Gf3rW9zPvXebi0Y9OKTURnRQ9YZu/v91J7cm3W6+59vJfIlAjRo6KHXXaiciTaE/Rt6GPXbbuwiNH8nuaspyIKbaLGovn9zfz1W39l5y92Qgbm/Mvoe+35zpDoSDD410Gic6OkelL7Sj9cGybVc+S+mhrNpHxD9cGtKc5dEKY8bFSXGecck93fuLs3JGmsNE46zJy8jE3/8/1Un1hNSWkJoWiI6hOqD/j97lW7IQS1p2ZXJJmhDB13d9D4rsai5nAZRzqeZs6X59D8nma2XrUV54K9UzBRY7FnzR6a39fMwu8spOX9LWz/yfaCZEgPptnywy00v7+ZUPTA562ZgWX1zzgiTMpyz9WDW9Ksei7FrO/GeO+tA6x5McVFtw8UO5aX9v5hL7GnYsz8+MzhJ2EWErsTJDoSbPzyRp77/HMk9ybZdPkmkt3JguaITIlQ01aDmQ3vsRukY+msMwRFLmPR/WA3NW01ANS8poaBF8b3vMkmg0s5tv5wK3Wn1lHbNvyHIFwb3vc4SHYnj5ipsmxMynI/bWaYuzakGEw54gnH3Ruye0n29TeUs+1z1Wz+TDU/vyDKWbPD3HDe4V/2y8FVzK8g9mSMTCJDejBN7MkYALE/x+j8TSdHX3I0JWXZP1TLZ5az6AeLWPDtBSz49gIiUyLMvWLuvpfjhcpRc2INfeuGz4Q91D6ESztC1cF+1TdRYxGpi9C3fngs+tb1UdpUOqEZnHNs/8l2ylrKaHjL/rn6mhNq6P5jNwDdf+ym5tU1Wf9bgs6/P1dj8JrWEO9YEOa4q/toqjKWNJVQW2bcsS7Jp38zSEe/4+039XNCcwm/vaiy2HG9VzGnguoTqtn45Y2Ea8OUzyinJFrCzht2kkll2PzNzQBE50Zp/VDrqOvZevVW+tb3kYqnWP/Z9TS+s5H619cXNMfBMtS9ro7tP97O8196HgsbMz42I+s93kKbqLGY/uHp7LxxeL7dIkbrh0e/P/ORof/5frr/t5uyGWVs/PJGAJouaKLh7Aa2/mgre/+wl8jUCDP/Yeb4ByugrJBzf21tbW7t2rUF295BrRh+WRZPOKpKjf6k43U/7WPlOVFOzPJN1dyzHProj8liyfVLSA+mCZWHyAxleOHrL9D6oda/efOsEIKQ4+mLny7o9l5pyfVLgGCMRRAyFPv+ADCzx5xzWZ3Ha1LuuQMsv2uAZzsyDKbg4uMjhS92OcCO63YwtH2ITDLDlNOnFKXYg5QjCIIwFkHIcKSatOV+0/nBPhRtspn5iWC8LA5KjiAIwlgEIcORalK+oSoi4juVu4iIh1TuIiIeUrmLiHhI5S4i4iGVu4iIh1TuIiIeUrmLiHhI5S4i4iGVu4iIh1TuIiIeUrmLiHhI5S4i4qFJV+4uIF+WGJQcMiLYX2k6Oek+ycmkK3cLyCMmKDlkhP7WBo/uk5xMunIXEZkMVO4iIh5SuYuIeEjlLiLiIZW7iIiHVO4iIh5SuYuIeChc7ABBcsszSVY8MMS6jgyP/H0lbdNDoy47mHK87qd9DKUhlYELFoW54szyAqb1X/vP2+l9shcLG6WNpcz46AxClaPfJ9t+vI3YkzHCNWHmf3U+ALtu20XvE72YGaGaEDM+NoPIlMiE5Thohjt2sfeBvYSrh59uTRc0UX18dVYZgiLXsdhy1RYSOxMApPvThCpCzLty3oRlGC3HwJYBdly/g8xQhtKppcz4xAxC0dHXcSRSub/M4sYSbr8wysfvHjzssmUhWHNxJVWlRjLtOP2nfbx1fopTZmhI86VycSVN727CQkb7L9vp+HUHzRc2j7r8lNOnMHXZVLZds23fdQ1va6Dp/CYAuu7rYvedu2n9UOuE5ThYBoCGNzfQ8NaGrLYbRLmOxVH/cNS+yztv3kmoIvtCzcfjYsdPd9D8nmYqF1ay9/d76bync9/jxBeTtomufGCIG55OMq3CmFlrnNQS4tKlZWO+vZlRVTp8OZmBZFofqMvF7jt30/2nbsLVYSL1EaKzogeUYcXcCnoe7TnkOioXVJLoSBxw3cv3xjJDGcwOfS/lmuNgGY5UEzkWzjl6Hu1h9j/NntAMo+UYah+iYkHF8O9fVUnnt/0r90k55/7o9jS3rUvy1Ccq+c0HKli7IzOu9aQzjhP+M07jN2O8cU6Yk7XXPi79L/TTu7aXef86j6M/dzQDmwf+Zpm9v99L9XHjm8rYdesu1n9uPd1/6qbxXY1FydH13108/y/Ps+3H20j3pbO+faFN9H3Sv6GfcE2YsubRd6gmMkNZaxmxx2MA9D7aS3JPMut1BN2kLPcHt6Y4d0GY8rBRXWacc8z4SjlUYjz5iSq2fa6aR3ak+cvu4D9pg6j/+X6qT6ympLSEUDRE9QkHPll3r9oNIag9tXZc62+6oImF31lI3al1dK3uKniOqWdN5ZhvHsO8f51HpDbCzp/vHNe/o5Am+j7peaiHupPripZhxkdm0LWmi42XbyQzmMFC/r3unpTlnm915caZs8LcuzFV7Cje2fuHvcSeijHz4zMPO6VyOLWn1tK7trfgOcK1YazEsBJjyuunMPDC3+6BHklyvU9c2tHzWA+1J4/vD0M+MpRNL2P2F2Yz74p51J5SS2lj6bizBNWkLPfTZoa5a0OKwZQjnnDcvSH7Uu7oy9A9OHxmx4Gk474XUixsmJTDmbOK+RXEnoyRSWRID6aJPTn8cjn25xidv+nk6EuOpqRsfGM71D6073Ls8RhlLaNPA0xUjmT3/pf8vY/3Ut4a/KOqJvI+iT8Tp6yljEj9oY9amsgMqd7h57zLODpWdVB/Zv241hNk5lzhTj3b1tbm1q5dW7DtHdSK4b2FFfcPctPTKZqqjMZK4y1zwzRUGJ/+zSAd/Y66cuOE5hJ+e1HlQVfz511pLv7VAOkMZBxc+KoIX3n92N+QHQ5x6DeCJosl1y9h1x276Hmoh3BtmHB1mKolVXTe00kmlSFcOTxtFp0bPeSRLluv3krf+j5S8RThmjCN72wk/uf4cMEblE4tZfqHph/yUMhccxwsQ9/6Pga3Dh+BVdowkqFu9AxPX/z0YcdsIi25fgkwMWNR//p6tl2zjYq5FdSfdfhCnajHRWYow57VewCoOalm+OibUV4BFPv+ADCzx5xzbVndZrKWezzhqCo1+pPDx6uvPCfKiS0FPs5V5Q4Ml0l6ME2oPERmKMMLX3+B1g+1Ep0VLXiWIOQodpm8VO5BGIsgZCj2/QHjK/dJe3jH8rsGeLYjw2AKLj4+UvhilwPsuG4HQ9uHyCQzTDl9SlGKPUg5giAIYxGEDEeqSVvuN51fUewI8jIzPzGz2BGA4OQIgiCMRRAyHKn0DqCIiIdU7iIiHlK5i4h4SOUuIuIhlbuIiIdU7iIiHlK5i4h4SOUuIuIhlbuIiIdyLnczC5nZE2Z2dz4CiYhI7vKx534JsC4P6xERkTzJqdzNbAbwduDa/MQREZF8yHXP/bvAPwGjfgmpmS03s7VmtrajoyPHzeXOBeRrrIOSIwhqQjXFjhAYQRiLIGQIiiN5LMZ9VkgzOxvY7Zx7zMzOGG0559xKYCUMn899vNvLF6PoEYDg5AiCBy96sNgR5GV0f/ghlz3304B3mNlm4OfAWWZ2Q15SiYhITsZd7s65LzrnZjjnZgHvBdY45y7KWzIRERk3HecuIuKhvHwTk3PufuD+fKxLRERypz13EREPqdxFRDykchcR8ZDK/WVueSbJq66KU3JFL2t3pA+57NaeDGde38exP4rzqqvifO+hoQKlFBE5vLy8oeqLxY0l3H5hlI/fPXjYZcMl8O03lXNiS4jYkOOklX28cW6YY6eFCpBUROTQJm25X/nAEDc8nWRahTGz1jipJcSlS8vGfPuW6hJaqocvV5cZi6aVsL3Xcey0CQosIpKFSVnuj25Pc9u6JE99opJkGk5c2cdJLePf497cneGJnWlOnqG9dhEJhklZ7g9uTXHugjDlYaM8DOccM/5hiCcc5/+yn+++pZyaMp0MTESCQW+o5iCZHi72DyyJcN6iSLHjiIjsMynL/bSZYe7akGIw5YgnHHdvSGW9DuccH101yKKGEJ87dexz9SIihTApp2Ve0xriHQvCHHd1H01VxpKmEmrLjDvWJfn0bwbp6He8/aZ+Tmgu4bcXVR50HQ9uTfOzPydZ0ljCCf8ZB+Bry8p423ztwYtI8U3Kcge4dGkZK84opz/peN1P+zhpeogTW0K8a4zTK6cfFcZdfuSeyF9E/DZpy335XQM825FhMAUXHx/hxByOlhERCZpJW+43nV9R7AgiIhNmUr6hKiLiO5W7iIiHVO4iIh5SuYuIeEjlLiLiIZW7iIiHVO4iIh5SuYuIeEjlLiLiIZW7iIiHVO4iIh5SuYuIeEjlLiLioUlX7onSKcWOAAQnh4j4adKd8rf0nzcXOwIApcUOICJem3R77iIik4HKXUTEQyp3EREPqdxFRDykchcR8ZDKXUTEQyp3EREPqdxFRDykchcR8ZDKXUTEQyp3EREPqdxFRDykchcR8ZDKXUTEQyp3EREPqdxFRDykchcR8ZDKXUTEQyp3EREPqdxFRDykchcR8ZDKXUTEQyp3EREPqdxFRDykchcR8ZDKXUTEQyp3EREPjbvczWymmf2PmT1rZs+Y2SX5DCYiIuMXzuG2KeDzzrnHzawaeMzM7nPOPZunbCIiMk7j3nN3zu10zj0+cjkGrANa8xVMRETGLy9z7mY2C3g18HA+1iciIrnJZVoGADOrAm4DPuOc6z3I75cDywEitdOYddmvc91kjhxgRc4AtWXGU1e8rdgxAuGRRx4hFosVNUN1dTWvfe1ri5oB4JmTT6ak52+eRgUVjGdIMHJkamt41cNH5j5rTuVuZhGGi/1G59ztB1vGObcSWAlQ1jLf5bK9/Cj2w2VYz1AAhiIgYrEYdXV1Rc3Q3d1d1O2/pNjFDkF5hgQjRxDuj/HK5WgZA34MrHPOfSd/kUREJFe5zLmfBvwdcJaZPTnyn+YZREQCYNzTMs65PxKMV04iIvIK+oSqiIiHVO4iIh5SuYuIeCjn49zzIT0Qo/POfyfVu4twTRMN77yMUHnVqMsPvPAYe1avhEyGquPfRO0p7y54js57vsvApkcJVdQy/aNX5WX7kptYLMaVV17Jpk2bMDO+8pWvcNxxxxU7Vl58v7ODNbE4ZjA1FOJrLS00hiOjLn/9nj3c2tONAceUlfHV5hbKSnLfl8smx5d27uSBvjj1oRCrZs8BoDud5vM7trM9maQ1EuE701upDYUmLMNoOb65ezf398WJYMwsjfDV5hZqsswRdIHYc+996BbKZx1P6/JrKJ91PL0P3TLqsi6TZs99V9P47iuY/rGr6Hv2ARKdWwqeo2rJG2h89xV52a7kx7e+9S2WLl3Kbbfdxs0338zs2bOLHSlvPjKlnl/Nns0ds2bz+qoqrursGnXZXckkN3Tv5ZajZ7Fq9hzSwD2x/ByvnU2Od9XWsnLGzAOuu7ari1MqKrl3zlxOqajk2j2j3z4fGUbLsbSykjtnzeZXs2czq7SUa8aRI+gKvufe/eDN9D17P6FoLaGaBkqb5tG/8WGa3vd1ACoXL2PXzV9kyhkfPujtEzs3EK5rIVLXPLz8otcx8PxDlDYcVdAc5TMXk+rZldU2ZeLE43GeeOIJVqxYAUAkEiESGX1vLsiu7uzkrt5e6sMhmsNhji0v5yP1U/f9fiDjDnuYWto5Bp0j7ByDmcwh92wnKkdbRQXbk4kDrlsTj3P9UcPP1XfW1nLxli18flrjhGUYLcdplZX7Lh9fHuW3Rf6E9EQoaLlnkoP0b/hfpn/4B7h0ip3XX0Jp0zzSfd2Eq+oBCFVOId03+qcFU7EuwjXT9v0cqm4gsfO5rHIM7dyQcw4Jlu3bt1NXV8cVV1zBhg0bWLRoEZdeeinRaLTY0bLy9MAAv4vHuGPWLFI4zt+8mWPLywH4bkcHq3p7qCop4bqZo+/MNEUifLi+nmWbNlJeUsLSisoDyqxQOQ6mK51iWni4dhpCIbrSqYJneKXbe7p5S3VNTusIooJOy7jEIBXzTsHCpZSUVRCd+7fn8jCzCT94fmjbukDkkPxJp9M899xzXHDBBdx0001Eo1Guu+66YsfK2hMDA5xVVUVZSQmVJSHOrNr/ns9npk1jzdx5nF1Ty43de0ddR086zZp4nPvmzOX+ufMYcBlW9fQUPMfhHO45VogM/9nVSciMc2pU7hMiVFlHKr4HgFR8DyWVo59nJFw9lVRvx76f07FOQlVTR11+onJIsDQ2NtLY2MjixYsBWLZsGevXry9yqolxdk0N9x1iGuFP/X20RiLUh8NEzHhjVTVPDg4UPMfBTA2F6UgN7613pFLUh3KbPBhPhpfc0dPNA/E4/9EyneGzqfiloOVupeUMbHoEl0qQSQwwsOlRACrmnUzfX1YD0PeX1VTMO3nUdZS2HENq7w6S3e24dJK+db8neojlD6ZsxqKcc0iwNDQ00NTUxObNm4HhM03OmTOnuKHG4dXRKPfH4wxlMvRlMtwfjwOwObF/znhNPMac0rJR19ESjvDUwAADmQzOOR7q72NOaWnBcxzMmVVV/GrkVcSveno4q2r0o+ImKgPAH/ri/HjPHn7UOoNoHo4iCiJzrnBnJyxrme+ic19D37MPEKqsI1RRR/nsE6lYsJTOO79BqreDcE0jDedeRihaPep6BjY9yp7V14DLULXkjdQufU/WWbr/eGNOOTpW/QdDW54mPdBLqKKO2tM/QPXxb8oqw+ZvvD3r3D5avXp1Xs4K+dxzz/Fv//ZvJJNJWltbufzyy6kZ48vt7u5uli1blnOGXK1buIgfdnbw695epobDTA2FOL2yij/2xXkxkaAEY3okzOVNzTQd4g3jH3R2cG8sRghYVF7OlU3NlGZZYrnmuHTHdh7p76c7nWZqOMynpjawrLqaz+7Yzs5kkukjh0LWHeIQxHyMxcFyrNzTRdK5fYdhHl8eZUVz80Fvv2j9uixGbWKY2WPOubasblPocm9639cpKY2SSQ6y66bLqH/zpyhrnlewDC/JJAaKnkPlPixf5Z6LIJV7XyZDZUkJA5kMH9yyhSuam/e9kVhIQcgRhAxHarkX/FDIrnt/SLJrCy6VpGrxWUUp9iDlEHmlFe3tbEwMkXCOc2tqi1LsQckRhAxHqoKX+7R3fKHQmzyooOQQeaVvTp9e7AhAMHIEIcORys93EkREJjmVu4iIh1TuIiIeUrmLiHhI5S4i4iGVu4iIh1TuIiIeUrmLiHhI5S4i4iGVu4iIh1TuIiIeUrmLiHhI5S4i4qGCnhUyFIhvsnIQgG9HrS0rfoag2LNnz75vUCqWsX6px0QLwqMzCBkgGDkK920X+VfQcj92ei1r9QUV8gr19fVF/0q87u7uom7/JcUuMwhGBghGjiBkGC9Ny4iIeEjlLiLiIZW7iIiHVO4iIh5SuYuIeEjlLiLiIZW7iIiHCnqcu8hEOuecc6ioqCAUChEKhfjZz35W7Eh58/3ODtbE4pjB1FCIr7W00BiOHHTZFxNDfG7Hjn0/b0sm+fTUBj5YX1/QHAA/27uHW7q7ccC7a+uKkuFLO3fyQF+c+lCIVbOHP09xb6yXH3V28kIiwS+OPprF5dGccwWNyl288l//9V/U1dUVO0befWRKPf/YMA0YLsyrOrtY0dx80GVnl5Zxx6zZAKSd44xNG1lWXV3wHM8PDXFLdze/OHoWETOWb9vK66uqOLq0tGAZAN5VW8sHpkzhsp37/+DNLy3j+62trGhvzylLkKncRQLm6s5O7urtpT4cojkc5tjycj5SP3Xf7wcybsyfnHyov5+jIqW0Rkbfs52oHJsSQxwXjRItGZ79fU20gv+Oxfjo1KmHuFV+MwC0VVSwPZk44Lq5ZWVjznCkUrmLN8yMT37yk5gZ5513Huedd16xI2Xt6YEBfhePccesWaRwnL95M8eWlwPw3Y4OVvX2UFVSwnUzjxrT+u7p7eVt4zhvTj5yzC8t43sdHXSn05SZ8fu+OK8aWUehMkxmekNVvHHttddy44038v3vf59bbrmFxx9/vNiRsvbEwABnVVVRVlJCZUmIM6uq9v3uM9OmsWbuPM6uqeXG7r2HXVfCOf6nL86bxzElk48cc8vK+Fj9VD62dQvLt21lYRe5XBEAAAWbSURBVFk5IRv72VryORaTkcpdvNHY2AgMn4jsjDPO4Jlnnilyoolxdk0N98Vih13uD/E4x5aV0RCemBfoY8lxfl0dt86azc+OOpqaUIhZkdzm28eTYbJSuYsXBgYG6Ovr23f54YcfZu7cuUVOlb1XR6PcH48zlMnQl8lwfzwOwObE/jnjNfEYc0oPP2d8T2x8UzL5zNGVSgGwI5nkv+Mx3p5FnnyOxWSkOXfxQldXF1/4whcASKfTvPnNb2bp0qVFTpW9JdEoZ1ZV8c7NLzI1HOaYsjKqS0L8v47dvJhIUIIxPRLm8qbRjw4B6M9k+N++PlYcZrmJznHJju10p9NEzPiXxiZqQqGCZ7h0x3Ye6e+nO53mzE0b+dTUBmpDIb66exd70mn+77ZtLCwr55qZM8ec7UhgzhXudPRtbW1u7dq1BdueHBlWr15d9MMXu7u7WbZsWVEzAKxbuIi+TIbKkhIGMhk+uGULVzQ373sjsZCCkCMIGRatX1fQ7R2MmT3mnGvL5jbacxcJmBXt7WxMDJFwjnNraotS7EHJEYQMRyqVu0jAfHP69GJHAIKRIwgZjlR6Q1VExEMqdxERD6ncRUQ8pHIXEfGQyl1ExEMqdxERD6ncRUQ8pHIXEfGQyl1ExEM5lbuZvcXMnjOzjWZ2Wb5CiYhIbsZd7mYWAn4EvBU4FnifmR2br2AiIjJ+uey5vxbY6Jx7wTmXAH4OnJufWCIikotcyr0V2Pqyn7eNXCciIkU24WeFNLPlwPKRH4fM7C8Tvc0jRAPQWewQAaGx2E9jsV8wxiKL732dQAuyvUEu5b4dePlXl8wYue4AzrmVwEoAM1ub7QnnfaWx2E9jsZ/GYj+NxX5mlvW3HOUyLfMoMN/MZptZKfBeYFUO6xMRkTwZ9567cy5lZp8CfguEgJ845/z8unkRkSNMTnPuzrl7gHuyuMnKXLbnGY3FfhqL/TQW+2ks9st6LAr6BdkiIlIYOv2AiIiHClLuOk3BMDObaWb/Y2bPmtkzZnZJsTMVm5mFzOwJM7u72FmKyczqzOxWM1tvZuvM7NRiZyoWM/vsyPPjL2Z2s5mVFztToZjZT8xs98sPGTezejO7z8yeH/n/lLGsa8LLXacpOEAK+Lxz7ljgFOCTk3gsXnIJsK7YIQLge8C9zrmFwPFM0jExs1bgH4E259xihg/WeG9xUxXUdcBbXnHdZcBq59x8YPXIz4dViD13naZghHNup3Pu8ZHLMYafwJP2U71mNgN4O3BtsbMUk5nVAq8DfgzgnEs457qLm6qowkDUzMJABbCjyHkKxjn3e2DPK64+F7h+5PL1wDvHsq5ClLtOU3AQZjYLeDXwcHGTFNV3gX8CMsUOUmSzgQ7gpyNTVNeaWWWxQxWDc2478C1gC7AT6HHO/a64qYquyTm3c+RyO9A0lhvpDdUiMLMq4DbgM8653mLnKQYzOxvY7Zx7rNhZAiAMnAhc7Zx7NdDHGF96+2ZkPvlchv/gTQcqzeyi4qYKDjd8eOOYDnEsRLmP6TQFk4WZRRgu9hudc7cXO08RnQa8w8w2MzxVd5aZ3VDcSEWzDdjmnHvpVdytDJf9ZPQG4EXnXIdzLgncDiwtcqZi22VmLQAj/989lhsVotx1moIRZmYMz6uuc859p9h5isk590Xn3Azn3CyGHxNrnHOTcg/NOdcObDWzl04OtQx4toiRimkLcIqZVYw8X5YxSd9cfplVwMUjly8G7hzLjSb8rJA6TcEBTgP+DnjazJ4cue6fRz7pK5Pbp4EbR3aAXgA+XOQ8ReGce9jMbgUeZ/josieYRJ9UNbObgTOABjPbBlwOfAP4pZl9FPgrcOGY1qVPqIqI+EdvqIqIeEjlLiLiIZW7iIiHVO4iIh5SuYuIeEjlLiLiIZW7iIiHVO4iIh76//1V4A9de/cWAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x432 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# 求めた解を元の変数に代入\n",
    "values = result[0].values\n",
    "solution = q.decode(values)\n",
    "draw_solutions(solution, tables, customer_groups, xmax=10, ymax=10, figsize=(6, 6))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "auIoYSpiqrOh"
   },
   "source": [
    "### 各目的関数の最終値を確認"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "h2TxupEv0sAH",
    "outputId": "0c34c32a-a207-460c-9906-cda46c664b70"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " g1: 0.0,\n",
      " g2: 4.583333333333328, \n",
      " g4: -11.546874999999998\n"
     ]
    }
   ],
   "source": [
    "val_g1 = g1.replace_all(values)\n",
    "val_g2 = g2.replace_all(values)\n",
    "val_g3 = g3.replace_all(values)\n",
    "print(f\" g1: {val_g1},\\n g2: {val_g2}, \\n g4: {val_g3}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "E7c69TENsWYK"
   },
   "source": [
    "## まとめ\n",
    "\n",
    "\n",
    "アニーリングマシンを用いて座席配置問題を解くために，イジングモデルを定義し適切に解を導出できることを確認できました。\n",
    "\n",
    "改善案としては，以下が挙げられます。\n",
    "\n",
    "- 定員オーバーの場合（座らせる席がない場合）を考慮する\n",
    "- 希望座席，カウンター希望などの希望条件を考慮する\n",
    "- 離着席のタイミングを考慮する（例：先に待っている４人を飛ばして，後のお一人様を通す。）\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "m5jsSw6GuQWc"
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "seat_allocation.ipynb",
   "provenance": [],
   "toc_visible": true
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}