Skip to content

Instantly share code, notes, and snippets.

@enakai00

enakai00/routing_enakai.ipynb

Created November 28, 2022 23:04
Show Gist options
  • Save enakai00/af1265697018d923c45c10ad5caaf26b to your computer and use it in GitHub Desktop.
Save enakai00/af1265697018d923c45c10ad5caaf26b to your computer and use it in GitHub Desktop.
Download ZIP
routing_enakai.ipynb
Display the source blob
Display the rendered blob
Raw
routing_enakai.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"id": "view-in-github",
"colab_type": "text"
},
"source": [
"<a href=\"https://colab.research.google.com/gist/enakai00/af1265697018d923c45c10ad5caaf26b/routing_enakai.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
]
},
{
"cell_type": "code",
"source": [
"!pip install pulp"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "Tvuu6u_dIxON",
"outputId": "6b2c8d0f-3d14-4be4-d360-b78539798409"
},
"id": "Tvuu6u_dIxON",
"execution_count": 1,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n",
"Requirement already satisfied: pulp in /usr/local/lib/python3.7/dist-packages (2.7.0)\n"
]
}
]
},
{
"cell_type": "markdown",
"source": [
"## データ準備"
],
"metadata": {
"id": "VKhLf33fdtKR"
},
"id": "VKhLf33fdtKR"
},
{
"cell_type": "code",
"source": [
"csv='''k,x,y,pk_flag\n",
"p,0.0,0.0,1\n",
"s1,0.5294729842620497,-0.39704418227290517,0\n",
"s2,2.9169254244093357,-0.30251055552369227,0\n",
"s3,0.13153180989381932,1.898977340473876,0\n",
"s4,-1.0910788858274902,-0.7099639895163461,0\n",
"s5,0.22512387100444256,-0.3958439493352311,0\n",
"s6,-1.4313175349061673,-0.24585181270510476,0\n",
"s7,-0.43059473640149176,0.7241659231313945,0\n",
"s8,-1.9977462353660331,-0.8402148452279417,0\n",
"s9,1.3816692113846043,2.228797208677574,0'''\n",
"with open('k.csv', 'w') as f:\n",
" f.write(csv)"
],
"metadata": {
"id": "uvL0eKZjIKzf"
},
"id": "uvL0eKZjIKzf",
"execution_count": 2,
"outputs": []
},
{
"cell_type": "code",
"execution_count": 3,
"id": "7607da2e-8a9e-45e4-b8a8-810fc94d68ba",
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 381
},
"id": "7607da2e-8a9e-45e4-b8a8-810fc94d68ba",
"outputId": "c2c18980-8770-4a8e-c695-4e266e9dbe40"
},
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"10\n"
]
},
{
"output_type": "execute_result",
"data": {
"text/plain": [
" k x y pk_flag\n",
"0 p 0.000000 0.000000 1\n",
"1 s1 0.529473 -0.397044 0\n",
"2 s2 2.916925 -0.302511 0\n",
"3 s3 0.131532 1.898977 0\n",
"4 s4 -1.091079 -0.709964 0\n",
"5 s5 0.225124 -0.395844 0\n",
"6 s6 -1.431318 -0.245852 0\n",
"7 s7 -0.430595 0.724166 0\n",
"8 s8 -1.997746 -0.840215 0\n",
"9 s9 1.381669 2.228797 0"
],
"text/html": [
"\n",
" <div id=\"df-128dfe28-6561-48c7-b321-f1b4eee2361a\">\n",
" <div class=\"colab-df-container\">\n",
" <div>\n",
"<style scoped>\n",
" .dataframe tbody tr th:only-of-type {\n",
" vertical-align: middle;\n",
" }\n",
"\n",
" .dataframe tbody tr th {\n",
" vertical-align: top;\n",
" }\n",
"\n",
" .dataframe thead th {\n",
" text-align: right;\n",
" }\n",
"</style>\n",
"<table border=\"1\" class=\"dataframe\">\n",
" <thead>\n",
" <tr style=\"text-align: right;\">\n",
" <th></th>\n",
" <th>k</th>\n",
" <th>x</th>\n",
" <th>y</th>\n",
" <th>pk_flag</th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>0</th>\n",
" <td>p</td>\n",
" <td>0.000000</td>\n",
" <td>0.000000</td>\n",
" <td>1</td>\n",
" </tr>\n",
" <tr>\n",
" <th>1</th>\n",
" <td>s1</td>\n",
" <td>0.529473</td>\n",
" <td>-0.397044</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>2</th>\n",
" <td>s2</td>\n",
" <td>2.916925</td>\n",
" <td>-0.302511</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>3</th>\n",
" <td>s3</td>\n",
" <td>0.131532</td>\n",
" <td>1.898977</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>4</th>\n",
" <td>s4</td>\n",
" <td>-1.091079</td>\n",
" <td>-0.709964</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>5</th>\n",
" <td>s5</td>\n",
" <td>0.225124</td>\n",
" <td>-0.395844</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>6</th>\n",
" <td>s6</td>\n",
" <td>-1.431318</td>\n",
" <td>-0.245852</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>7</th>\n",
" <td>s7</td>\n",
" <td>-0.430595</td>\n",
" <td>0.724166</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>8</th>\n",
" <td>s8</td>\n",
" <td>-1.997746</td>\n",
" <td>-0.840215</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>9</th>\n",
" <td>s9</td>\n",
" <td>1.381669</td>\n",
" <td>2.228797</td>\n",
" <td>0</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"</div>\n",
" <button class=\"colab-df-convert\" onclick=\"convertToInteractive('df-128dfe28-6561-48c7-b321-f1b4eee2361a')\"\n",
" title=\"Convert this dataframe to an interactive table.\"\n",
" style=\"display:none;\">\n",
" \n",
" <svg xmlns=\"http://www.w3.org/2000/svg\" height=\"24px\"viewBox=\"0 0 24 24\"\n",
" width=\"24px\">\n",
" <path d=\"M0 0h24v24H0V0z\" fill=\"none\"/>\n",
" <path d=\"M18.56 5.44l.94 2.06.94-2.06 2.06-.94-2.06-.94-.94-2.06-.94 2.06-2.06.94zm-11 1L8.5 8.5l.94-2.06 2.06-.94-2.06-.94L8.5 2.5l-.94 2.06-2.06.94zm10 10l.94 2.06.94-2.06 2.06-.94-2.06-.94-.94-2.06-.94 2.06-2.06.94z\"/><path d=\"M17.41 7.96l-1.37-1.37c-.4-.4-.92-.59-1.43-.59-.52 0-1.04.2-1.43.59L10.3 9.45l-7.72 7.72c-.78.78-.78 2.05 0 2.83L4 21.41c.39.39.9.59 1.41.59.51 0 1.02-.2 1.41-.59l7.78-7.78 2.81-2.81c.8-.78.8-2.07 0-2.86zM5.41 20L4 18.59l7.72-7.72 1.47 1.35L5.41 20z\"/>\n",
" </svg>\n",
" </button>\n",
" \n",
" <style>\n",
" .colab-df-container {\n",
" display:flex;\n",
" flex-wrap:wrap;\n",
" gap: 12px;\n",
" }\n",
"\n",
" .colab-df-convert {\n",
" background-color: #E8F0FE;\n",
" border: none;\n",
" border-radius: 50%;\n",
" cursor: pointer;\n",
" display: none;\n",
" fill: #1967D2;\n",
" height: 32px;\n",
" padding: 0 0 0 0;\n",
" width: 32px;\n",
" }\n",
"\n",
" .colab-df-convert:hover {\n",
" background-color: #E2EBFA;\n",
" box-shadow: 0px 1px 2px rgba(60, 64, 67, 0.3), 0px 1px 3px 1px rgba(60, 64, 67, 0.15);\n",
" fill: #174EA6;\n",
" }\n",
"\n",
" [theme=dark] .colab-df-convert {\n",
" background-color: #3B4455;\n",
" fill: #D2E3FC;\n",
" }\n",
"\n",
" [theme=dark] .colab-df-convert:hover {\n",
" background-color: #434B5C;\n",
" box-shadow: 0px 1px 3px 1px rgba(0, 0, 0, 0.15);\n",
" filter: drop-shadow(0px 1px 2px rgba(0, 0, 0, 0.3));\n",
" fill: #FFFFFF;\n",
" }\n",
" </style>\n",
"\n",
" <script>\n",
" const buttonEl =\n",
" document.querySelector('#df-128dfe28-6561-48c7-b321-f1b4eee2361a button.colab-df-convert');\n",
" buttonEl.style.display =\n",
" google.colab.kernel.accessAllowed ? 'block' : 'none';\n",
"\n",
" async function convertToInteractive(key) {\n",
" const element = document.querySelector('#df-128dfe28-6561-48c7-b321-f1b4eee2361a');\n",
" const dataTable =\n",
" await google.colab.kernel.invokeFunction('convertToInteractive',\n",
" [key], {});\n",
" if (!dataTable) return;\n",
"\n",
" const docLinkHtml = 'Like what you see? Visit the ' +\n",
" '<a target=\"_blank\" href=https://colab.research.google.com/notebooks/data_table.ipynb>data table notebook</a>'\n",
" + ' to learn more about interactive tables.';\n",
" element.innerHTML = '';\n",
" dataTable['output_type'] = 'display_data';\n",
" await google.colab.output.renderOutput(dataTable, element);\n",
" const docLink = document.createElement('div');\n",
" docLink.innerHTML = docLinkHtml;\n",
" element.appendChild(docLink);\n",
" }\n",
" </script>\n",
" </div>\n",
" </div>\n",
" "
]
},
"metadata": {},
"execution_count": 3
}
],
"source": [
"import pandas as pd\n",
"k_dfm = pd.read_csv('k.csv')\n",
"print(len(k_dfm))\n",
"k_dfm"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "9eff1e7b-94f2-499c-89ba-a0ca700b3eff",
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 262
},
"id": "9eff1e7b-94f2-499c-89ba-a0ca700b3eff",
"outputId": "805155ce-c4d5-4578-a3f9-04d111974dec"
},
"outputs": [
{
"output_type": "display_data",
"data": {
"text/plain": [
"<Figure size 432x288 with 1 Axes>"
],
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAD1CAYAAABTL05uAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAatElEQVR4nO3de3BV9d3v8feXiwS5BDlESwAFhot4uNWToh50hmItCDxqFRVLvKAHZ7C2fcZnInJEO2WcQWEqlQcNA9Si4oVHrZQChpOnYoueioSUiwpIDk8rIVhDwQQjosHv+SN7x50YIJeVvXb2+rxmMsm6ZK3vGvST3/6u397L3B0REUl/7cIuQEREkkOBLyISEQp8EZGIUOCLiESEAl9EJCIU+CIiEaHAF5EmMbPxZlZsZu+Z2TNm1iHsmqRxFPgi0mhm1g54Bpjm7sOBvwO3h1uVNJYCX0ROycy6mNl6M9thZu8BNwJfuvuHsV0KgRvCq1CaQoEvIqczEShz91GxEX0B0MHMcmLbpwL9QqtOmkSBLyKnswu4ysweM7Mr3L0CmAYsMrN3gWPAyVArlEazVP0snV69enn//v3DLkMk8qqrq6moqODw4cN069aN7Ozs2m2VlZUcPnyYgQMHhlihJNq2bdthd89qaFvK3l3v378/RUVFYZchEmllZWX07NmTjIwM1q1bx4oVK1i2bBnnnnsuJ06cYNKkSSxdupTx48eHXarEmNnfT7UtZQNfRMK3a9cu8vLyaNeuHR07diQ/P5+FCxeybt06vv76a2bNmqWwb0NStqWTk5PjGuGLiDSNmW1z95yGtummrYhIRCjwRaSO+q/6U7ULIE2nwBeRWgv/6xAPlxysDXl35+GSgyz8r0MhVyZBUOCLCFAT7pXVJ1leerg29B8uOcjy0sNUVp/USD8NaJaOiABgZswb1AeA5aWHWV56GICZfXsxb1AfzCzM8iQAGuGLSK3E0I9T2KcPBb6I1Iq3cRIl9vSlbVPgiwhAnZ79zL69ODRuFDP79qrT05e2TT18EQFq2jndO7Sv07OPt3e6d2ivtk4aUOCLSK28Ab1x99pwj4e+wj49qKUjInXUD3eFffpQ4IuIRIQCXyLrrrvuYtSoUYwcOZKpU6fy2WefhV2SSKtS4EtkLVq0iB07drBz507OP/98lixZEnZJIq1KgS+RUFVVxeTJkxk1ahTDhw9n9erVdO/eHaiZjnj8+HH1qiXtaZaOREJBQQHZ2dmsX78egIqKCgBmzJjBhg0buOiii/jVr34VZokira7FI3wz62dmm8zsAzN738x+3sA+ZmaLzazEzHaa2cUtPa9IU4wYMYLCwkJmz57N5s2byczMBOC3v/0tZWVlDBs2jNWrV4dcpUjrCqKlUw38m7tfBFwK/MTMLqq3z9XA4NjX3UB+AOcVabQhQ4ZQXFzMiBEjmDt3LvPmzavd1r59e6ZNm8arr74aYoUira/Fge/uh9y9OPbzMWA30KfebtcCz3qNd4AeZta7pecWaayysjLOPvtscnNzycvLY9u2bZSUlAA1Pfy1a9dy4YUXhlylSOsKtIdvZv2B7wJb6m3qAxxIWC6NravzVAUzu5uaVwCcf/75QZYmEVf/YdxPPvkkt99+O5WVlbg7o0aNIj9fLzwlvQUW+GbWFXgV+Fd3r2zOMdx9GbAMah5iHlRtIhMmTGDChAl11r399tshVSMSjkCmZZpZR2rC/nl3/10DuxwE+iUs942tExGRJAlilo4BvwF2u/vjp9htLXBbbLbOpUCFu+shmdLq9EBukW8E0dIZC9wK7DKz7bF1/xs4H8DdlwIbgElACfA5MCOA84qcVvm/L+HksUrOmzMHM8Pd+cf8+bTv1p2sn94bdnkiSdfiwHf3t4DTvkXRa4ZVP2npuUQay905eaySo88+B8B5c+bwj/nzOfrsc5xz2611PgJYJCr0TltJS2bGeXPmAHD02edqg/+c226tHfGLRI0+S0fSVmLoxynsJcoU+JK24j37RP+YP183biWyFPiSluJhH+/ZX7j7A8657VaOPvucQl8iSz18SUtmRvtu3ev07OPtnfbduqutI5FkqTrSycnJ8aKiorDLkDau/mwczc6RdGdm29w9p6FtaulIWtMDuUW+ocAXEYkIBb6ISEQo8EVEIkKBLyISEQp8EZGIUOCLiESEAl9EJCIU+CIiEaHAFxGJCAW+iEhEKPBFRCJCgS8iEhEKfBGRiFDgi4hEhAJfRCQiAgl8M3vazD4xs/dOsX2cmVWY2fbY18NBnFdERBovqEccrgSWAM+eZp/N7j4loPOJiEgTBTLCd/c/A0eCOJaIiLSOZPbwLzOzHWb2upn994Z2MLO7zazIzIrKy8uTWJqISPpLVuAXAxe4+yjg34E1De3k7svcPcfdc7KyspJUmohINCQl8N290t0/i/28AehoZr2ScW4REamRlMA3s++YmcV+HhM77z+TcW4REakRyCwdM3sRGAf0MrNS4BdARwB3XwpMBWaZWTVwHJjm7h7EuUVEpHECCXx3v+UM25dQM21TRERConfaiohEhAJfRCQiFPgiIhGhwBcRiQgFvohIRCjwRUQiQoEvIhIRCnwRkYhQ4IuIRIQCX0QkIhT4IiIRocAXEYkIBb6ISEQo8EVEIkKBLyISEQp8EZGIUOCLiESEAl9EJCIU+CIiEaHAFxGJCAW+iEhEBBL4Zva0mX1iZu+dYruZ2WIzKzGznWZ2cRDnFRGRxgtqhL8SmHia7VcDg2NfdwP5AZ1XREQaKZDAd/c/A0dOs8u1wLNe4x2gh5n1DuLcIiLSOMnq4fcBDiQsl8bWiYhIkqTUTVszu9vMisysqLy8POxyRETSSrIC/yDQL2G5b2xdHe6+zN1z3D0nKysrSaWJiERDsgJ/LXBbbLbOpUCFux9K0rlFRAToEMRBzOxFYBzQy8xKgV8AHQHcfSmwAZgElACfAzOCOK+0PVdccQXHjh0D4JNPPmHMmDGsWbMm5KpEoiGQwHf3W86w3YGfBHEuads2b95c+/MNN9zAtddeG2I1ItGSUjdtJb1UVVUxefJkRo0axfDhw1m9enXttsrKSt544w2uu+66ECsUiZZARvgiDSkoKCA7O5v169cDUFFRUbttzZo1XHnllXTv3j2s8kQiRyN8aTUjRoygsLCQ2bNns3nzZjIzM2u3vfjii9xyy2k7gSISMAW+tJohQ4ZQXFzMiBEjmDt3LvPmzQPg8OHDvPvuu0yePDnkCkWiRS0daTVlZWX07NmT3NxcevTowYoVKwB45ZVXmDJlChkZGSFXKBItCnxpNbt27SIvL4927drRsWNH8vNrPjPvpZde4oEHHgi5OpHosZoZk6knJyfHi4qKwi5DRKRNMbNt7p7T0Db18EVEIkKBL4Gr/6oxVV9FikSNAl8CtWnTJgoKCmpD3t0pKChg06ZNIVcmIgp8CYy788UXX7Bly5ba0C8oKGDLli188cUXGumLhEyzdCQwZsbEiTVPutyyZQtbtmwB4JJLLmHixImYWZjliUSeRvgSqMTQj1PYi6QGBb4EKt7GSZTY0xeR8KilI4FJ7NnH2zjxZdBIXyRsCnwJjJmRkZFRp2cfb+9kZGQo7EVCpsCXQH3/+9/H3WvDPR76CnuR8KmHL4GrH+4Ke5HUoMAXEYkIBb6ISEQo8EVEIkKBLyISEYEEvplNNLO9ZlZiZt96soWZ3WFm5Wa2Pfb1v4I4r4iINF6Lp2WaWXvgSeAqoBTYamZr3f2Deruudvd7W3o+ERFpniBG+GOAEnff7+5fAi8B1wZwXBERCVAQgd8HOJCwXBpbV98NZrbTzF4xs34BnFdERJogWTdt/wD0d/eRQCHwTEM7mdndZlZkZkXl5eVJKk1EJBqCCPyDQOKIvW9sXS13/6e7n4gtrgD+R0MHcvdl7p7j7jlZWVkBlCYiInFBBP5WYLCZDTCzs4BpwNrEHcysd8LiNcDuAM4rIiJN0OJZOu5ebWb3AhuB9sDT7v6+mc0Ditx9LfAzM7sGqAaOAHe09LwiItI0lqoPpsjJyfGioqKwyxARaVPMbJu75zS0Te+0FRGJCAW+iEhEKPBFRCJCgS8iEhEKfBGRiFDgi4hEhAJfRCQiFPgiIhGhwBcRiQgFvohIRCjwRUQiQoEvIhIRCnwRkYhQ4IuIRIQCX9LC3/72Ny688EKmT5/OsGHDmDp1Kp9//nnYZYmkFAW+pI29e/dyzz33sHv3brp3785TTz0VdkkiKUWBL2mjX79+jB07FoDc3FzeeuutkCsSSS0KfEkbZnbaZZGoU+BL2vjoo4/4y1/+AsALL7zA5ZdfHnJFIqlFgS9pY+jQoTz55JMMGzaMo0ePMmvWrLBLEkkpHcIuQCQoHTp0YNWqVWGXIZKyNMIXEYmIQALfzCaa2V4zKzGzBxrY3snMVse2bzGz/kGcVySuf//+vPfee2GXIZLSWtzSMbP2wJPAVUApsNXM1rr7Bwm73QUcdfdBZjYNeAy4uaXnlmhb89eDLNy4l7JPj5PdozN5E4Zy3Xf7hF2WSMoKYoQ/Bihx9/3u/iXwEnBtvX2uBZ6J/fwKcKVpzpy0wJq/HmTO73Zx8NPjOHDw0+PM+d0u1vz1YNiliaSsIAK/D3AgYbk0tq7Bfdy9GqgA/lsA55aIWrhxL8e/Olln3fGvTrJw496QKhJJfSl109bM7jazIjMrKi8vD7scSWFlnx5v0noRCSbwDwL9Epb7xtY1uI+ZdQAygX/WP5C7L3P3HHfPycrKCqC01OXuPPjggwwZMoRhw4axePHisEtqU7J7dG7SehEJJvC3AoPNbICZnQVMA9bW22ctcHvs56nAG+7uAZy7zVq5ciUHDhxgz5497N69m2nTpoVdUpuSN2EonTu2r7Ouc8f25E0YGlJFIqmvxbN03L3azO4FNgLtgafd/X0zmwcUufta4DfAc2ZWAhyh5o9CZFRVVXHTTTdRWlrKyZMneeihh8jPz+eFF16gXbuav7nnnntuyFW2LfHZOJqlI9J4lqoD7ZycHC8qKgq7jEC8+uqrFBQUsHz5cgAqKioYOHAg9913H6+99hpZWVksXryYwYMHh1ypiLR1ZrbN3XMa2pZSN23T1YgRIygsLGT27Nls3ryZzMxMTpw4QUZGBkVFRcycOZM777wz7DJFJMVNnz6doUOHMnz4cO68806++uqrJv2+Aj8JhgwZQnFxMSNGjGDu3LnMmzePvn37cv311wPwox/9iJ07d4ZcpYikuunTp7Nnzx527drF8ePHWbFiRZN+Xx+elgRlZWX07NmT3NxcevTowYoVK7juuuvYtGkTAwYM4E9/+hNDhgwJu0wRSSEN3fu7+eZvPqBgzJgxlJaWNumYCvwk2LVrF3l5ebRr146OHTuSn5/PoEGDmD59OosWLaJr165N/kstIumtoKCA7Oxs1q9fD9Tc+4v76quveO6553jiiSeadEzdtBURSUEffvghP/zhD7n55puZMmUKV1xxRe22mTNn0qVLF379619/6/d001ZEpI1p6N4fwC9/+UvKy8t5/PHHm3xMBX4rqv/qKVVfTUldd9xxBwMGDGD06NGMHj2a7du3N/tYS5YsYdCgQZgZhw8fDrBKSXdlZWWcffbZ5ObmkpeXR3FxMStWrGDjxo28+OKLte/haQr18FtJReHf8S+qyZwyEDPD3alYtx/L6EDmVReEXZ6cwcKFC5k6dWqLjzN27FimTJnCuHHjWl6UREpD9/4uvfRSLrjgAi677DIArr/+eh5++OFGH1OB3wrcHf+ims/eLgMgc8pAKtbt57O3y+g6Nht3R58OnRoamgkR5LESZ1WINMWECROYMGFCnXXV1dUtOqYCvxWYGZlTBgLw2dtltcHfdWx27YhfUkNDMyFef/11HnzwQebNm8eVV17Jo48+SqdOnZp1LJFUoh5+K0kM/TiFfepp6F3Q8+fPZ8+ePWzdupUjR47w2GOPNftYIk3R2vf9FPitJN6zT1Sxbr9u3KaYhmZC9O7dGzOjU6dOzJgxg3fffbfZxxJprKe2P8WCrQtqM8LdWbB1AU9tfyqwc6il0wriYR/v2Sf28EEj/VTS0LugDx06RO/evXF31qxZw/Dhw5t9LJHGcHeOfXmMVbtXAXD/9+5nwdYFrNq9itxhuYHd91PgtwIzwzI61OnZx9s7ltFBYZ9CGpoJMX36dMrLy3F3Ro8ezdKlS5t9rMWLF7NgwQI+/vhjRo4cyaRJk/SHQL7FzLj/e/cDsGr3qtrgzx2Wy/3fuz+wzNA7bVtR/b/Kmp0jIqfj7ox8dmTt8s7bdjY5M/RO25DU/4dS2IvIqcR79okSe/pBUOBL5AQ6E6L+76boK2ZJbfGwj/fsd962k9xhuazavSrQ0FcPXyLl/778PCeqqhh3+8zad0C/+cxyOnXpwv+8cXrTDrZpPnxRARPng1lN2BfMgYxM+P6c1rkASUtmRrezutXp2cd7+t3O6hZYd0CBL5Hh7pyoqqL49bUAjLt9Jm8+s5zi19dy8dXXNO0ei3tN2G/Jr1meOL8m7LfkwyWzararhSdNcM/oe+r8NxgP/SBbwQp8iQwzY9ztMwEofn1tbfBffPU1tSP+JhysJuShJuTjwX/JrG9G/CJN1Nr3/dTDl0hJDP24Jof9Nwf7JvTjFPaSwhT4Einxnn2iN59Z3rybYvGefaKCObpxKymrRYFvZj3NrNDM9sW+n3OK/U6a2fbY19qWnFOkueJhH+/Z3/fSH7j46msofn1t00M/Hvbxnv0vPq35viVfoS8pq6U9/AeAP7r7o2b2QGx5dgP7HXf30S08l0iLmBmdunSp07OPt3c6denS9B5+Rmbdnn28vZORqbaOpKQWvdPWzPYC49z9kJn1Bt5096EN7PeZu3dtyrHT4Z22kpoCfQd0/dk4mp0jIWvNd9qe5+6HYj9/DJx3iv0yzKzIzN4xs+taeE45g5/97Gd07dqkv6+REuhMiPq/q7CXFHbGlo6Z/SfwnQY2PZi44O5uZqd6uXCBux80s4HAG2a2y93/XwPnuhu4G+D8888/Y/HybUVFRRw9ejTsMkQkBZ1xhO/uP3D34Q18/R74R6yVQ+z7J6c4xsHY9/3Am8B3T7HfMnfPcfecrKysZl5SNFRVVTF58mRGjRrF8OHDWb16NSdPniQvL48FCxac+QAiEjktvWm7FrgdeDT2/ff1d4jN3Pnc3U+YWS9gLKBEaqGGHqe3ZMkSrrnmGnr37h1ydSKSilraw38UuMrM9gE/iC1jZjlmFv/Q72FAkZntADYBj7r7By08b+TVf5xeVVUVL7/8Mj/96U/DLk1EUpQ+D78NO3LkCBs2bGD58uWMHz+e/Px8MjIyAPjoo48YOHAgJSUlIVcpIsl0ulk6+iydNqqhx+l9/PHHtdu7du2qsBeROhT4bVRDj9MTETmdSLV0/vjHP5KXl8fXX39N165dWblyJYMGDQr0HCIiYdIjDmNmzZrF888/z/bt2/nxj3/MI488EnZJIiJJk7YtnaqqKm666SZKS0s5efIkDz30EGZGZWUlUDONMTs7O+Qqm04PRheR5krbwG9onnp2djaTJk2ic+fOdO/enXfeeSfkKpvm3T/s58Txai6/cXDt4/neenkfnTp3YMy/DAy7PBFJcWnb0qk/Tz0zM5NFixaxYcMGSktLmTFjBvfdd1/YZTaau3PieDU73yjlrZf31Yb9zjdKOXG8OtAn24tIekrbEf6QIUMoLi5mw4YNzJ07l/Hjx7Njxw4uueQSAG6++WYmTpwYcpWNZ2ZcfuNgAHa+UcrON0oBGDm+b+2IX0TkdNJ2hF9WVsbZZ59Nbm4ueXl5bN26lYqKCj788EMACgsLGTZsWMhVNk1i6Mcp7EWksdJ2hN/QPPUDBw5www030K5dO8455xyefvrpsMtskngbJ9FbL+9T6ItIo0RqHn5bltizj7dx6i8r9EVEH62QBsyMTp071An3eHunU+cOCnsROaO0C/x0nqc+5l8G1rmeeOiny/WJSOtKq5u2+/c/wb59j9ROUXR39u17hP37nwi5suAE+ng+EYmUtAl8d6e6upIDpStrQ3/fvkc4ULqS6upKzVMXkchLm5aOmTF48FwADpSu5EDpSgD69b2DwYPnaiQsIpGXNiN8qBv6cQp7EZEaaRX48TZOosSevohIlKVN4Cf27Pv1vYPx3y+hX9876vT0RUSiLK16+B06dK/Ts4+3dzp06K62johEXtoEPsDAgT//1jx19fBFRGqkTUsnTvPURUQalnaBLyIiDVPgi4hEhAJfRCQiFPgiIhGRsp+Hb2blwN9bcIhewOGAymkronjNoOuOGl336V3g7lkNbUjZwG8pMys61UMA0lUUrxl03WHXkWy67uZTS0dEJCIU+CIiEZHOgb8s7AJCEMVrBl131Oi6mylte/giIlJXOo/wRUQkQdoGvpktNLM9ZrbTzF4zsx5h15QMZnajmb1vZl+bWdrPZDCziWa218xKzOyBsOtJBjN72sw+MbP3wq4lmcysn5ltMrMPYv+N/zzsmpLBzDLM7F0z2xG77l8291hpG/hAITDc3UcCHwJzQq4nWd4Drgf+HHYhrc3M2gNPAlcDFwG3mNlF4VaVFCuBiWEXEYJq4N/c/SLgUuAnEfn3PgGMd/dRwGhgopld2pwDpW3gu/v/cffq2OI7QN8w60kWd9/t7nvDriNJxgAl7r7f3b8EXgKuDbmmVufufwaOhF1Hsrn7IXcvjv18DNgN9Am3qtbnNT6LLXaMfTXr5mvaBn49dwKvh12EBK4PcCBhuZQIBICAmfUHvgtsCbeS5DCz9ma2HfgEKHT3Zl13m34Aipn9J/CdBjY96O6/j+3zIDUvBZ9PZm2tqTHXLZKuzKwr8Crwr+5eGXY9yeDuJ4HRsXuRr5nZcHdv8j2cNh347v6D0203szuAKcCVnkbzT8903RFyEOiXsNw3tk7SlJl1pCbsn3f334VdT7K5+6dmtomaezhNDvy0bemY2UTgfuAad/887HqkVWwFBpvZADM7C5gGrA25JmklVvP4ut8Au9398bDrSRYzy4rPMjSzzsBVwJ7mHCttAx9YAnQDCs1su5ktDbugZDCzH5lZKXAZsN7MNoZdU2uJ3ZS/F9hIzQ28/3D398OtqvWZ2YvAX4ChZlZqZneFXVOSjAVuBcbH/p/ebmaTwi4qCXoDm8xsJzWDnEJ3X9ecA+mdtiIiEZHOI3wREUmgwBcRiQgFvohIRCjwRUQiQoEvIhIRCnwRkYhQ4IuIRIQCX0QkIv4/9KimeIWtIScAAAAASUVORK5CYII=\n"
},
"metadata": {
"needs_background": "light"
}
}
],
"source": [
"import matplotlib.pyplot as plt\n",
"fig = plt.subplot()\n",
"fig.set_aspect('equal') \n",
"for row in k_dfm.itertuples():\n",
" if row.pk_flag:\n",
" fig.scatter(row.x,row.y,marker='o')\n",
" else:\n",
" fig.scatter(row.x,row.y,marker='x')\n",
" fig.annotate(row.k, (row.x, row.y+0.1))\n",
"plt.show()"
]
},
{
"cell_type": "code",
"source": [
"csv='''k1,k2,t\n",
"p,p,0.0\n",
"p,s1,0.6618048985464831\n",
"p,s2,2.9325699595693937\n",
"p,s3,1.903527135779046\n",
"p,s4,1.3017303874107433\n",
"p,s5,0.4553824651008621\n",
"p,s6,1.4522785543897057\n",
"p,s7,0.8425129739306184\n",
"p,s8,2.1672450270010017\n",
"p,s9,2.6223170683761907\n",
"s1,p,0.6618048985464831\n",
"s1,s1,0.0\n",
"s1,s2,2.3893232850645365\n",
"s1,s3,2.33025149097131\n",
"s1,s4,1.6504869491807492\n",
"s1,s5,0.3043514798712115\n",
"s1,s6,1.966610940851162\n",
"s1,s7,1.4760901492526832\n",
"s1,s8,2.5657819900688335\n",
"s1,s9,2.7606668433461263\n",
"s2,p,2.9325699595693937\n",
"s2,s1,2.3893232850645365\n",
"s2,s2,0.0\n",
"s2,s3,3.5503473835679253\n",
"s2,s4,4.028661918273781\n",
"s2,s5,2.6934191514343575\n",
"s2,s6,4.34861208276556\n",
"s2,s7,3.5014219709795844\n",
"s2,s8,4.943998728414635\n",
"s2,s9,2.9604949986001756\n",
"s3,p,1.903527135779046\n",
"s3,s1,2.33025149097131\n",
"s3,s2,3.5503473835679253\n",
"s3,s3,0.0\n",
"s3,s4,2.881206652884047\n",
"s3,s5,2.2967290275659575\n",
"s3,s6,2.65382557280395\n",
"s3,s7,1.3023701932891987\n",
"s3,s8,3.469437825388361\n",
"s3,s9,1.2929132484695316\n",
"s4,p,1.3017303874107433\n",
"s4,s1,1.6504869491807492\n",
"s4,s2,4.028661918273781\n",
"s4,s3,2.881206652884047\n",
"s4,s4,0.0\n",
"s4,s5,1.3531670616503215\n",
"s4,s6,0.5754671589164339\n",
"s4,s7,1.578913524545914\n",
"s4,s8,0.9159754189566711\n",
"s4,s9,3.840677092945487\n",
"s5,p,0.4553824651008621\n",
"s5,s1,0.3043514798712115\n",
"s5,s2,2.6934191514343575\n",
"s5,s3,2.2967290275659575\n",
"s5,s4,1.3531670616503215\n",
"s5,s5,0.0\n",
"s5,s6,1.6632184980530935\n",
"s5,s7,1.297840131341717\n",
"s5,s8,2.266851782298962\n",
"s5,s9,2.868159398061737\n",
"s6,p,1.4522785543897057\n",
"s6,s1,1.966610940851162\n",
"s6,s2,4.34861208276556\n",
"s6,s3,2.65382557280395\n",
"s6,s4,0.5754671589164339\n",
"s6,s5,1.6632184980530935\n",
"s6,s6,0.0\n",
"s6,s7,1.393693125219608\n",
"s6,s8,0.8210413431334596\n",
"s6,s9,3.746569392636121\n",
"s7,p,0.8425129739306184\n",
"s7,s1,1.4760901492526832\n",
"s7,s2,3.5014219709795844\n",
"s7,s3,1.3023701932891987\n",
"s7,s4,1.578913524545914\n",
"s7,s5,1.297840131341717\n",
"s7,s6,1.393693125219608\n",
"s7,s7,0.0\n",
"s7,s8,2.2143285684647966\n",
"s7,s9,2.3554651179522046\n",
"s8,p,2.1672450270010017\n",
"s8,s1,2.5657819900688335\n",
"s8,s2,4.943998728414635\n",
"s8,s3,3.469437825388361\n",
"s8,s4,0.9159754189566711\n",
"s8,s5,2.266851782298962\n",
"s8,s6,0.8210413431334596\n",
"s8,s7,2.2143285684647966\n",
"s8,s8,0.0\n",
"s8,s9,4.56500643468924\n",
"s9,p,2.6223170683761907\n",
"s9,s1,2.7606668433461263\n",
"s9,s2,2.9604949986001756\n",
"s9,s3,1.2929132484695316\n",
"s9,s4,3.840677092945487\n",
"s9,s5,2.868159398061737\n",
"s9,s6,3.746569392636121\n",
"s9,s7,2.3554651179522046\n",
"s9,s8,4.56500643468924\n",
"s9,s9,0.0'''\n",
"with open('kk.csv', 'w') as f:\n",
" f.write(csv)\n"
],
"metadata": {
"id": "jM3PsKgKIVny"
},
"id": "jM3PsKgKIVny",
"execution_count": 5,
"outputs": []
},
{
"cell_type": "code",
"execution_count": 6,
"id": "a1d3ecf3-19e6-414b-987a-22c6383537a5",
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 225
},
"id": "a1d3ecf3-19e6-414b-987a-22c6383537a5",
"outputId": "dab546d9-2ab0-4633-abd0-64330638e8db"
},
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"100\n"
]
},
{
"output_type": "execute_result",
"data": {
"text/plain": [
" k1 k2 t\n",
"0 p p 0.000000\n",
"1 p s1 0.661805\n",
"2 p s2 2.932570\n",
"3 p s3 1.903527\n",
"4 p s4 1.301730"
],
"text/html": [
"\n",
" <div id=\"df-86e638a4-5141-4f72-8d23-b20925b06f13\">\n",
" <div class=\"colab-df-container\">\n",
" <div>\n",
"<style scoped>\n",
" .dataframe tbody tr th:only-of-type {\n",
" vertical-align: middle;\n",
" }\n",
"\n",
" .dataframe tbody tr th {\n",
" vertical-align: top;\n",
" }\n",
"\n",
" .dataframe thead th {\n",
" text-align: right;\n",
" }\n",
"</style>\n",
"<table border=\"1\" class=\"dataframe\">\n",
" <thead>\n",
" <tr style=\"text-align: right;\">\n",
" <th></th>\n",
" <th>k1</th>\n",
" <th>k2</th>\n",
" <th>t</th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>0</th>\n",
" <td>p</td>\n",
" <td>p</td>\n",
" <td>0.000000</td>\n",
" </tr>\n",
" <tr>\n",
" <th>1</th>\n",
" <td>p</td>\n",
" <td>s1</td>\n",
" <td>0.661805</td>\n",
" </tr>\n",
" <tr>\n",
" <th>2</th>\n",
" <td>p</td>\n",
" <td>s2</td>\n",
" <td>2.932570</td>\n",
" </tr>\n",
" <tr>\n",
" <th>3</th>\n",
" <td>p</td>\n",
" <td>s3</td>\n",
" <td>1.903527</td>\n",
" </tr>\n",
" <tr>\n",
" <th>4</th>\n",
" <td>p</td>\n",
" <td>s4</td>\n",
" <td>1.301730</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"</div>\n",
" <button class=\"colab-df-convert\" onclick=\"convertToInteractive('df-86e638a4-5141-4f72-8d23-b20925b06f13')\"\n",
" title=\"Convert this dataframe to an interactive table.\"\n",
" style=\"display:none;\">\n",
" \n",
" <svg xmlns=\"http://www.w3.org/2000/svg\" height=\"24px\"viewBox=\"0 0 24 24\"\n",
" width=\"24px\">\n",
" <path d=\"M0 0h24v24H0V0z\" fill=\"none\"/>\n",
" <path d=\"M18.56 5.44l.94 2.06.94-2.06 2.06-.94-2.06-.94-.94-2.06-.94 2.06-2.06.94zm-11 1L8.5 8.5l.94-2.06 2.06-.94-2.06-.94L8.5 2.5l-.94 2.06-2.06.94zm10 10l.94 2.06.94-2.06 2.06-.94-2.06-.94-.94-2.06-.94 2.06-2.06.94z\"/><path d=\"M17.41 7.96l-1.37-1.37c-.4-.4-.92-.59-1.43-.59-.52 0-1.04.2-1.43.59L10.3 9.45l-7.72 7.72c-.78.78-.78 2.05 0 2.83L4 21.41c.39.39.9.59 1.41.59.51 0 1.02-.2 1.41-.59l7.78-7.78 2.81-2.81c.8-.78.8-2.07 0-2.86zM5.41 20L4 18.59l7.72-7.72 1.47 1.35L5.41 20z\"/>\n",
" </svg>\n",
" </button>\n",
" \n",
" <style>\n",
" .colab-df-container {\n",
" display:flex;\n",
" flex-wrap:wrap;\n",
" gap: 12px;\n",
" }\n",
"\n",
" .colab-df-convert {\n",
" background-color: #E8F0FE;\n",
" border: none;\n",
" border-radius: 50%;\n",
" cursor: pointer;\n",
" display: none;\n",
" fill: #1967D2;\n",
" height: 32px;\n",
" padding: 0 0 0 0;\n",
" width: 32px;\n",
" }\n",
"\n",
" .colab-df-convert:hover {\n",
" background-color: #E2EBFA;\n",
" box-shadow: 0px 1px 2px rgba(60, 64, 67, 0.3), 0px 1px 3px 1px rgba(60, 64, 67, 0.15);\n",
" fill: #174EA6;\n",
" }\n",
"\n",
" [theme=dark] .colab-df-convert {\n",
" background-color: #3B4455;\n",
" fill: #D2E3FC;\n",
" }\n",
"\n",
" [theme=dark] .colab-df-convert:hover {\n",
" background-color: #434B5C;\n",
" box-shadow: 0px 1px 3px 1px rgba(0, 0, 0, 0.15);\n",
" filter: drop-shadow(0px 1px 2px rgba(0, 0, 0, 0.3));\n",
" fill: #FFFFFF;\n",
" }\n",
" </style>\n",
"\n",
" <script>\n",
" const buttonEl =\n",
" document.querySelector('#df-86e638a4-5141-4f72-8d23-b20925b06f13 button.colab-df-convert');\n",
" buttonEl.style.display =\n",
" google.colab.kernel.accessAllowed ? 'block' : 'none';\n",
"\n",
" async function convertToInteractive(key) {\n",
" const element = document.querySelector('#df-86e638a4-5141-4f72-8d23-b20925b06f13');\n",
" const dataTable =\n",
" await google.colab.kernel.invokeFunction('convertToInteractive',\n",
" [key], {});\n",
" if (!dataTable) return;\n",
"\n",
" const docLinkHtml = 'Like what you see? Visit the ' +\n",
" '<a target=\"_blank\" href=https://colab.research.google.com/notebooks/data_table.ipynb>data table notebook</a>'\n",
" + ' to learn more about interactive tables.';\n",
" element.innerHTML = '';\n",
" dataTable['output_type'] = 'display_data';\n",
" await google.colab.output.renderOutput(dataTable, element);\n",
" const docLink = document.createElement('div');\n",
" docLink.innerHTML = docLinkHtml;\n",
" element.appendChild(docLink);\n",
" }\n",
" </script>\n",
" </div>\n",
" </div>\n",
" "
]
},
"metadata": {},
"execution_count": 6
}
],
"source": [
"kk_dfm = pd.read_csv('kk.csv')\n",
"print(len(kk_dfm))\n",
"kk_dfm.head()"
]
},
{
"cell_type": "code",
"source": [
"csv='''r,s,w,b,e\n",
"r00,s4,1000,17,18\n",
"r01,s1,950,16,18\n",
"r02,s6,1330,2,4\n",
"r03,s5,1130,19,20\n",
"r04,s2,710,1,2\n",
"r05,s5,690,10,12\n",
"r06,s3,1180,13,15\n",
"r07,s4,690,4,6\n",
"r08,s2,960,16,17\n",
"r09,s6,930,14,15\n",
"r10,s9,910,16,17\n",
"r11,s3,1100,8,9\n",
"r12,s1,1360,12,14\n",
"r13,s7,1120,19,20\n",
"r14,s9,820,9,10\n",
"r15,s3,650,16,17\n",
"r16,s5,1590,16,17\n",
"r17,s7,930,15,16\n",
"r18,s4,880,13,14\n",
"r19,s9,1470,9,10\n",
"r20,s6,1020,2,4\n",
"r21,s8,2020,19,20\n",
"r22,s4,790,10,11\n",
"r23,s9,890,5,7\n",
"r24,s2,1160,14,16\n",
"r25,s3,560,2,3\n",
"r26,s5,1440,16,18\n",
"r27,s5,900,6,8\n",
"r28,s2,1230,14,16\n",
"r29,s4,1020,4,5\n",
"r30,s4,1020,16,18\n",
"r31,s1,1080,6,8\n",
"r32,s7,1110,8,10\n",
"r33,s8,1840,7,8\n",
"r34,s5,690,18,19\n",
"r35,s6,980,18,20\n",
"r36,s1,1220,11,12\n",
"r37,s7,1230,10,12\n",
"r38,s7,1360,16,18\n",
"r39,s2,890,15,17\n",
"r40,s4,1130,19,20\n",
"r41,s3,1450,18,19\n",
"r42,s7,870,19,20\n",
"r43,s5,1290,6,7\n",
"r44,s2,620,6,8\n",
"r45,s9,970,17,19\n",
"r46,s9,1060,1,3\n",
"r47,s7,860,2,4\n",
"r48,s2,1680,9,11\n",
"r49,s9,1250,13,15\n",
"r50,s7,1090,18,19\n",
"r51,s7,850,8,10\n",
"r52,s6,970,16,17\n",
"r53,s9,890,1,3\n",
"r54,s5,780,6,8\n",
"r55,s5,520,19,20\n",
"r56,s4,480,4,6\n",
"r57,s8,880,2,4\n",
"r58,s6,830,19,20\n",
"r59,s3,690,14,16\n",
"r60,s2,1100,18,20\n",
"r61,s7,1200,13,15\n",
"r62,s1,1090,17,18\n",
"r63,s5,560,19,20\n",
"r64,s7,780,6,7\n",
"r65,s8,1170,2,3\n",
"r66,s8,950,7,9\n",
"r67,s1,1120,6,8\n",
"r68,s7,1240,17,19\n",
"r69,s2,1040,10,11\n",
"r70,s1,1260,15,17\n",
"r71,s2,970,11,12\n",
"r72,s3,940,13,15\n",
"r73,s3,1060,5,6\n",
"r74,s1,1310,5,7\n",
"r75,s2,740,8,9\n",
"r76,s3,630,16,18\n",
"r77,s3,880,1,3\n",
"r78,s4,1270,2,3\n",
"r79,s9,910,5,7\n",
"r80,s6,1560,2,3\n",
"r81,s7,990,6,8\n",
"r82,s2,590,8,9\n",
"r83,s2,1770,18,20\n",
"r84,s2,650,10,11\n",
"r85,s8,1160,18,19\n",
"r86,s6,900,15,17\n",
"r87,s1,1060,15,17\n",
"r88,s2,770,18,20\n",
"r89,s5,780,17,18\n",
"r90,s7,850,7,9\n",
"r91,s2,1190,7,9\n",
"r92,s7,1580,18,20\n",
"r93,s6,910,4,5\n",
"r94,s1,900,16,18\n",
"r95,s3,1290,13,14\n",
"r96,s5,700,4,5\n",
"r97,s9,1270,13,14\n",
"r98,s9,1100,10,12\n",
"r99,s9,850,1,3'''\n",
"with open('r.csv', 'w') as f:\n",
" f.write(csv)\n",
"\n"
],
"metadata": {
"id": "_l1QvXdRIm_y"
},
"id": "_l1QvXdRIm_y",
"execution_count": 7,
"outputs": []
},
{
"cell_type": "code",
"execution_count": 8,
"id": "742e9e6a-4881-4a43-93d7-a46c8ef1c9c0",
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 225
},
"id": "742e9e6a-4881-4a43-93d7-a46c8ef1c9c0",
"outputId": "3bb0bef6-2b84-488a-a493-d4ae8306161a"
},
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"100\n"
]
},
{
"output_type": "execute_result",
"data": {
"text/plain": [
" r s w b e\n",
"0 r00 s4 1000 17 18\n",
"1 r01 s1 950 16 18\n",
"2 r02 s6 1330 2 4\n",
"3 r03 s5 1130 19 20\n",
"4 r04 s2 710 1 2"
],
"text/html": [
"\n",
" <div id=\"df-ba4db529-971c-4e71-a73d-ff6e7823d92e\">\n",
" <div class=\"colab-df-container\">\n",
" <div>\n",
"<style scoped>\n",
" .dataframe tbody tr th:only-of-type {\n",
" vertical-align: middle;\n",
" }\n",
"\n",
" .dataframe tbody tr th {\n",
" vertical-align: top;\n",
" }\n",
"\n",
" .dataframe thead th {\n",
" text-align: right;\n",
" }\n",
"</style>\n",
"<table border=\"1\" class=\"dataframe\">\n",
" <thead>\n",
" <tr style=\"text-align: right;\">\n",
" <th></th>\n",
" <th>r</th>\n",
" <th>s</th>\n",
" <th>w</th>\n",
" <th>b</th>\n",
" <th>e</th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>0</th>\n",
" <td>r00</td>\n",
" <td>s4</td>\n",
" <td>1000</td>\n",
" <td>17</td>\n",
" <td>18</td>\n",
" </tr>\n",
" <tr>\n",
" <th>1</th>\n",
" <td>r01</td>\n",
" <td>s1</td>\n",
" <td>950</td>\n",
" <td>16</td>\n",
" <td>18</td>\n",
" </tr>\n",
" <tr>\n",
" <th>2</th>\n",
" <td>r02</td>\n",
" <td>s6</td>\n",
" <td>1330</td>\n",
" <td>2</td>\n",
" <td>4</td>\n",
" </tr>\n",
" <tr>\n",
" <th>3</th>\n",
" <td>r03</td>\n",
" <td>s5</td>\n",
" <td>1130</td>\n",
" <td>19</td>\n",
" <td>20</td>\n",
" </tr>\n",
" <tr>\n",
" <th>4</th>\n",
" <td>r04</td>\n",
" <td>s2</td>\n",
" <td>710</td>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"</div>\n",
" <button class=\"colab-df-convert\" onclick=\"convertToInteractive('df-ba4db529-971c-4e71-a73d-ff6e7823d92e')\"\n",
" title=\"Convert this dataframe to an interactive table.\"\n",
" style=\"display:none;\">\n",
" \n",
" <svg xmlns=\"http://www.w3.org/2000/svg\" height=\"24px\"viewBox=\"0 0 24 24\"\n",
" width=\"24px\">\n",
" <path d=\"M0 0h24v24H0V0z\" fill=\"none\"/>\n",
" <path d=\"M18.56 5.44l.94 2.06.94-2.06 2.06-.94-2.06-.94-.94-2.06-.94 2.06-2.06.94zm-11 1L8.5 8.5l.94-2.06 2.06-.94-2.06-.94L8.5 2.5l-.94 2.06-2.06.94zm10 10l.94 2.06.94-2.06 2.06-.94-2.06-.94-.94-2.06-.94 2.06-2.06.94z\"/><path d=\"M17.41 7.96l-1.37-1.37c-.4-.4-.92-.59-1.43-.59-.52 0-1.04.2-1.43.59L10.3 9.45l-7.72 7.72c-.78.78-.78 2.05 0 2.83L4 21.41c.39.39.9.59 1.41.59.51 0 1.02-.2 1.41-.59l7.78-7.78 2.81-2.81c.8-.78.8-2.07 0-2.86zM5.41 20L4 18.59l7.72-7.72 1.47 1.35L5.41 20z\"/>\n",
" </svg>\n",
" </button>\n",
" \n",
" <style>\n",
" .colab-df-container {\n",
" display:flex;\n",
" flex-wrap:wrap;\n",
" gap: 12px;\n",
" }\n",
"\n",
" .colab-df-convert {\n",
" background-color: #E8F0FE;\n",
" border: none;\n",
" border-radius: 50%;\n",
" cursor: pointer;\n",
" display: none;\n",
" fill: #1967D2;\n",
" height: 32px;\n",
" padding: 0 0 0 0;\n",
" width: 32px;\n",
" }\n",
"\n",
" .colab-df-convert:hover {\n",
" background-color: #E2EBFA;\n",
" box-shadow: 0px 1px 2px rgba(60, 64, 67, 0.3), 0px 1px 3px 1px rgba(60, 64, 67, 0.15);\n",
" fill: #174EA6;\n",
" }\n",
"\n",
" [theme=dark] .colab-df-convert {\n",
" background-color: #3B4455;\n",
" fill: #D2E3FC;\n",
" }\n",
"\n",
" [theme=dark] .colab-df-convert:hover {\n",
" background-color: #434B5C;\n",
" box-shadow: 0px 1px 3px 1px rgba(0, 0, 0, 0.15);\n",
" filter: drop-shadow(0px 1px 2px rgba(0, 0, 0, 0.3));\n",
" fill: #FFFFFF;\n",
" }\n",
" </style>\n",
"\n",
" <script>\n",
" const buttonEl =\n",
" document.querySelector('#df-ba4db529-971c-4e71-a73d-ff6e7823d92e button.colab-df-convert');\n",
" buttonEl.style.display =\n",
" google.colab.kernel.accessAllowed ? 'block' : 'none';\n",
"\n",
" async function convertToInteractive(key) {\n",
" const element = document.querySelector('#df-ba4db529-971c-4e71-a73d-ff6e7823d92e');\n",
" const dataTable =\n",
" await google.colab.kernel.invokeFunction('convertToInteractive',\n",
" [key], {});\n",
" if (!dataTable) return;\n",
"\n",
" const docLinkHtml = 'Like what you see? Visit the ' +\n",
" '<a target=\"_blank\" href=https://colab.research.google.com/notebooks/data_table.ipynb>data table notebook</a>'\n",
" + ' to learn more about interactive tables.';\n",
" element.innerHTML = '';\n",
" dataTable['output_type'] = 'display_data';\n",
" await google.colab.output.renderOutput(dataTable, element);\n",
" const docLink = document.createElement('div');\n",
" docLink.innerHTML = docLinkHtml;\n",
" element.appendChild(docLink);\n",
" }\n",
" </script>\n",
" </div>\n",
" </div>\n",
" "
]
},
"metadata": {},
"execution_count": 8
}
],
"source": [
"r_dfm = pd.read_csv('r.csv')\n",
"print(len(r_dfm))\n",
"r_dfm.head()"
]
},
{
"cell_type": "code",
"execution_count": 9,
"id": "3cbacd2e-5819-4b3b-af2a-3bb21fc92d51",
"metadata": {
"id": "3cbacd2e-5819-4b3b-af2a-3bb21fc92d51"
},
"outputs": [],
"source": [
"import pandas as pd\n",
"k_dfm = pd.read_csv('k.csv')\n",
"kk_dfm = pd.read_csv('kk.csv')\n",
"r_dfm = pd.read_csv('r.csv')\n",
"\n",
"D = list(range(r_dfm.b.min(), r_dfm.e.max()+1))\n",
"p = k_dfm[k_dfm.pk_flag==1].k.tolist()[0]\n",
"S = k_dfm[k_dfm.pk_flag==0].k.tolist()\n",
"K = [p] + S\n",
"R = r_dfm.r.tolist()\n",
"\n",
"R2s = {row.r:row.s for row in r_dfm.itertuples()} # request to store\n",
"R2W = {row.r:row.w for row in r_dfm.itertuples()} # request to weight\n",
"R2B = {row.r:row.b for row in r_dfm.itertuples()} # request to begin day\n",
"R2E = {row.r:row.e for row in r_dfm.itertuples()} # request to end day\n",
"KK2T = {(row.k1, row.k2):row.t for row in kk_dfm.itertuples()} # kyoten1, kyoten2 to time"
]
},
{
"cell_type": "markdown",
"source": [
"## 巡回セールスマン問題の解（効率的な配送ルート）を事前に列挙"
],
"metadata": {
"id": "FqofM2eKdx83"
},
"id": "FqofM2eKdx83"
},
{
"cell_type": "code",
"execution_count": 10,
"id": "9248fcb9-bd4a-4155-9725-423d56e5f88b",
"metadata": {
"id": "9248fcb9-bd4a-4155-9725-423d56e5f88b"
},
"outputs": [],
"source": [
"import pulp\n",
"\n",
"def tsp(p, S, KK2T):\n",
" K = [p] + S\n",
" KK = [(k1,k2) for k1 in K for k2 in K]\n",
" \n",
" prob = pulp.LpProblem('tsp', pulp.LpMinimize)\n",
" x = pulp.LpVariable.dicts('x', KK, cat='Binary')\n",
" u = pulp.LpVariable.dicts('u', K, cat='Integer', lowBound=0)\n",
"\n",
" for k1 in K:\n",
" prob += pulp.lpSum([x[k1,k2] for k2 in K]) == 1\n",
" prob += pulp.lpSum([x[k2,k1] for k2 in K]) == 1\n",
"\n",
" prob += u[p] == 0\n",
" for s in S:\n",
" prob += 1 <= u[s]\n",
" prob += u[s] <= len(K) - 1\n",
" \n",
" for s1 in S:\n",
" for s2 in S:\n",
" prob += u[s1] + 1 <= u[s2] + (len(K) - 1) * (1 - x[s1,s2])\n",
"\n",
" # 労働時間は11時間以内\n",
" prob += pulp.lpSum(KK2T[k1,k2] * x[k1,k2] for k1 in K for k2 in K) <= 11\n",
" \n",
" # 目的関数は労働(移動)時間の最小化\n",
" prob += pulp.lpSum(KK2T[k1,k2] * x[k1,k2] for k1 in K for k2 in K)\n",
"\n",
" solver = pulp.PULP_CBC_CMD(msg=0) # CBCの標準出力を非表示\n",
" status = prob.solve(solver) \n",
"\n",
" if status==1:\n",
" X = [(k1,k2) for k1 in K for k2 in K if x[k1,k2].value() == 1]\n",
" t = sum([KK2T[k1,k2] for k1, k2 in X])\n",
" else:\n",
" X = []\n",
" t = -1\n",
" return status, X, t"
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "14754953-f386-4540-a92b-da026f7ae0a7",
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "14754953-f386-4540-a92b-da026f7ae0a7",
"outputId": "255b22c5-c626-4d05-8c9b-2c7ae1d31dd4"
},
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"status: Optimal\n",
"x: [('p', 's4'), ('s4', 's5'), ('s5', 's9'), ('s9', 'p')]\n",
"work_time: 8.145373915498993\n"
]
}
],
"source": [
"testS = ['s4','s5','s9']\n",
"status, X, t = tsp(p, testS, KK2T) \n",
"print('status:', pulp.LpStatus[status])\n",
"print('x:', X)\n",
"print('work_time:', t)"
]
},
{
"cell_type": "code",
"execution_count": 12,
"id": "254a76af-d2d6-4da6-aedb-b0e332229834",
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "254a76af-d2d6-4da6-aedb-b0e332229834",
"outputId": "ebdc8f75-6e19-4a28-d783-d57fb58a5c26"
},
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"status: Infeasible\n",
"route: []\n",
"time: -1\n"
]
}
],
"source": [
"testS = ['s1','s2','s3','s4','s5','s9']\n",
"status, X, t = tsp(p, testS, KK2T) \n",
"print('status:', pulp.LpStatus[status])\n",
"print('route:', X)\n",
"print('time:', t)"
]
},
{
"cell_type": "code",
"source": [
"from itertools import combinations\n",
"\n",
"Pat = []\n",
"Stp2Pat = {}\n",
"\n",
"for n in range(len(S)+1): \n",
" # お店の集合Sからn個選ぶ組合せを列挙\n",
" for Stp in combinations(S, n):\n",
" # 駐車場pとn個のお店(Stp)の巡回セールスマン問題を解く\n",
" status, X, t = tsp(p, list(Stp), KK2T) \n",
" \n",
" # 解が存在するときのみ配送ルートとして採用\n",
" if status == 1 :\n",
" Pat.append((Stp, X, t)) \n",
" Stp2Pat[Stp] = (Stp, X, t) \n",
" #print(Stp, X)\n",
" print('n:{} Pat:{}'.format(n, len(Pat)))\n",
" \n",
"for pat in Pat[:4]:\n",
" print(pat)"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "JbIeY78bSxT2",
"outputId": "baa7805e-bc05-43fb-dccd-83919b01297d"
},
"id": "JbIeY78bSxT2",
"execution_count": 13,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"n:0 Pat:1\n",
"n:1 Pat:10\n",
"n:2 Pat:46\n",
"n:3 Pat:127\n",
"n:4 Pat:234\n",
"n:5 Pat:317\n",
"n:6 Pat:354\n",
"n:7 Pat:363\n",
"n:8 Pat:364\n",
"n:9 Pat:364\n",
"((), [('p', 'p')], 0.0)\n",
"(('s1',), [('p', 's1'), ('s1', 'p')], 1.3236097970929661)\n",
"(('s2',), [('p', 's2'), ('s2', 'p')], 5.865139919138787)\n",
"(('s3',), [('p', 's3'), ('s3', 'p')], 3.807054271558092)\n"
]
}
]
},
{
"cell_type": "markdown",
"source": [
"## リクエストの組み合わせを起点として配送パターンを列挙した実装"
],
"metadata": {
"id": "eVbQa2Aod997"
},
"id": "eVbQa2Aod997"
},
{
"cell_type": "code",
"source": [
"from itertools import combinations\n",
"max_weight = 4000\n",
"\n",
"# 各日における配送可能な注文リストの作成\n",
"D2R = {d:[] for d in D}\n",
"for row in r_dfm.itertuples():\n",
" for d in range(row.b, row.e+1):\n",
" D2R[d].append(row.r)\n",
"\n",
"# 各日における配送パターンのリストの作成\n",
"D2P = {d:[] for d in D}\n",
"for d in D:\n",
" tarR = D2R[d] # 配送候補となる注文のリスト\n",
" for n in range(len(tarR)+1): # n（=0〜全部）個の注文を配送\n",
" for delR in combinations(tarR, n): # 配送する注文の組み合わせを列挙\n",
" # 重量オーバーの組み合わせはスキップ\n",
" w = sum([R2W[r] for r in delR])\n",
" if w > max_weight:continue\n",
"\n",
" # 配送対象のお店を抽出\n",
" tarStp = set()\n",
" for r in delR: \n",
" tarStp.add(R2s[r])\n",
" tarStp = tuple(sorted(list(tarStp))) # Stp2Pat のキーはソート済みのお店のタプル\n",
"\n",
" if tarStp not in Stp2Pat:continue # 対象のお店を回る配送ルートがなければスキップ\n",
"\n",
" # 配送パターン追加\n",
" _ , X, wt = Stp2Pat[tarStp]\n",
" new_pat = (X, wt, delR) # 配送ルート, 労働時間, 配送する注文\n",
" D2P[d].append(new_pat)\n",
" print('day:{} pat:{}'.format(d, len(D2P[d])))"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "AMiLcmCwPmF6",
"outputId": "c5ec8c29-bdd9-40fa-bacd-de1563ea4951"
},
"id": "AMiLcmCwPmF6",
"execution_count": 14,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"day:1 pat:31\n",
"day:2 pat:614\n",
"day:3 pat:503\n",
"day:4 pat:269\n",
"day:5 pat:260\n",
"day:6 pat:1371\n",
"day:7 pat:1143\n",
"day:8 pat:1461\n",
"day:9 pat:332\n",
"day:10 pat:345\n",
"day:11 pat:175\n",
"day:12 pat:44\n",
"day:13 pat:93\n",
"day:14 pat:333\n",
"day:15 pat:557\n",
"day:16 pat:2737\n",
"day:17 pat:3292\n",
"day:18 pat:2416\n",
"day:19 pat:2244\n",
"day:20 pat:575\n"
]
}
]
},
{
"cell_type": "code",
"execution_count": 15,
"id": "2dbcc212-592f-4cf8-b04f-4463adb64482",
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "2dbcc212-592f-4cf8-b04f-4463adb64482",
"outputId": "53fc7735-4a98-414a-abc1-530707434dff"
},
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"Q: 18795\n"
]
}
],
"source": [
"q_no = 0\n",
"Q = []\n",
"D2Q = {d:[] for d in D}\n",
"Q2R = {}\n",
"Q2h = {}\n",
"Q2t = {}\n",
"Q2X = {}\n",
"\n",
"for d in D:\n",
" for X,wt,delR in D2P[d]:\n",
" q_no += 1\n",
" q_name = 'q{:d}'.format(q_no)\n",
" Q.append(q_name)\n",
" D2Q[d].append(q_name)\n",
" Q2R[q_name] = delR\n",
" Q2h[q_name] = max(wt-8, 0) \n",
" Q2t[q_name] = wt\n",
" Q2X[q_name] = X\n",
"print('Q:', len(Q))"
]
},
{
"cell_type": "code",
"execution_count": 16,
"id": "ea09abdc-24d8-480d-aefd-c4a261ef849f",
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "ea09abdc-24d8-480d-aefd-c4a261ef849f",
"outputId": "e2ae508c-9283-46ff-908a-6c1f46b3cc9d"
},
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"status: Optimal\n",
"zangyo_cost:8213\n",
"gaityu_cost:1098940\n",
"total_cost:1107153\n",
"work_time:123\n"
]
}
],
"source": [
"import pulp\n",
"\n",
"prob = pulp.LpProblem('vrp_enum', pulp.LpMinimize)\n",
"\n",
"x = {}\n",
"for d in D:\n",
" for q in D2Q[d]:\n",
" x[d,q] = pulp.LpVariable('x_{}_{}'.format(d,q), cat='Binary')\n",
"y = pulp.LpVariable.dicts('y', R, cat='Continues', lowBound=0, upBound=1)\n",
"\n",
"for d in D:\n",
" prob += pulp.lpSum([x[d,q] for q in D2Q[d]]) == 1\n",
" \n",
"for r in R: \n",
" prob += y[r] + pulp.lpSum([x[d,q] for d in D for q in D2Q[d] if r in Q2R[q]]) >= 1\n",
"\n",
"zangyo = pulp.lpSum([3000 * Q2h[q] * x[d,q] for d in D for q in D2Q[d]])\n",
"gaityu = pulp.lpSum([46 * R2W[r] * y[r] for r in R])\n",
"work_time = pulp.lpSum([x[d,q]*Q2t[q] for d in D for q in D2Q[d]])\n",
"prob += zangyo + gaityu + work_time\n",
"\n",
"# 求解\n",
"solver = pulp.PULP_CBC_CMD(msg=1)\n",
"status = prob.solve(solver) \n",
"print('status:', pulp.LpStatus[status])\n",
"\n",
"# 結果の取得\n",
"zc = sum([3000 * Q2h[q] * x[d,q].value() for d in D for q in D2Q[d]])\n",
"gc = sum([46 * R2W[r] * y[r].value() for r in R])\n",
"wt = sum([x[d,q].value()*Q2t[q] for d in D for q in D2Q[d]])\n",
"print('zangyo_cost:{:.0f}'.format(zc))\n",
"print('gaityu_cost:{:.0f}'.format(gc))\n",
"print('total_cost:{:.0f}'.format(zc+gc))\n",
"print('work_time:{:.0f}'.format(wt))"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"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.10.8"
},
"colab": {
"provenance": [],
"include_colab_link": true
}
},
"nbformat": 4,
"nbformat_minor": 5
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment