割当問題のハンガリアン法をPythonで csvファイルを読み取って行う

Question

画像のようなCSVファイルを読み取り、ハンガリアン法（https://qiita.com/masa0599/items/47491e2e4ddb8e45f4eb）を行いたいのですが，Python初心者なため教えていただけないでしょうか．

その時，距離の総和の最小と最大それぞれの場合の
支援者と高齢者のいる住宅番号の組み合わせ，距離がわかるようにしたいです．

URLにハンガリアン法のコードはあります。
↓画像の補足
1行目に支援者がいる住宅番号，A列に高齢者がいる住宅番号を記載しております．A列に1が2つあるのは，高齢者が住宅番号１に2人存在するためです．
つまり，支援者は1～5の住宅に1人ずつというような感じです．
B2-F5は距離です

Answer 1

１．以下のスクリプトを作成し、Wariate.py という名で保存してください。

import csv
import sys
from munkres import Munkres
import numpy as np
import copy

def pout(mtx,ansMtx1,ansMtx2):
    arrs = []
    for idx1,idx2 in zip(ansMtx1,ansMtx2):
        arr = []
        arr.append(idx1[0])
        arr.append(idx1[1])
        arr.append(mtx[idx1])
        arr.append(idx2[0])
        arr.append(idx2[1])
        arr.append(mtx[idx2])
        arrs.append(arr)
    return arrs

if len(sys.argv) != 3:
    print(sys.argv[0],"P1 P2",file=sys.stderr)
    print("P1:input CSVfile",file=sys.stderr)
    print("P2:output CSVfile",file=sys.stderr)
    sys.exit(1)

mtx = np.loadtxt(sys.argv[1],delimiter=',',dtype='int32')
ansMtx1 = Munkres().compute(copy.copy(mtx))
asum1 = sum([mtx[idx] for idx in ansMtx1])

mtx_max = mtx * (-1)
ansMtx2 = Munkres().compute(copy.copy(mtx_max))
asum2 = sum([mtx[idx] for idx in ansMtx2])

arrs = pout(mtx,ansMtx1,ansMtx2)
np.savetxt(sys.argv[2],arrs,fmt='%d',delimiter=',')
print(f"STATUS=OK Min sum = {asum1} Max sum={asum2}")
sys.exit(0)

２．以下のマクロを標準モジュールに登録してください。
下記のフォルダ名は、私の環境でしけんしたものです。
Const pyscript As String = "D:\goo\python\goo_高齢者支援\Wariate.py"
Const infile As String = "D:\goo\python\goo_高齢者支援\INPUT.csv"
Const outfile As String = "D:\goo\python\goo_高齢者支援\OUTPUT.csv"
あなたの環境にあわせて、適切に設定してください。
３．下記のシートを作成してください。
シート名：高齢者支援
シート名：実行結果
４．マクロを実行すると
高齢者支援に記述されたデータを読み取り、その結果が実行結果に格納されます。
又、高齢者支援に色づけされます。
（最短：緑、最長：黄、最短と最長の両方共有：赤）
実行結果の2行は見出しです。あなたが、予め、作成しておいてください。

Option Explicit

Public Sub 高齢者支援()
    Const pyscript As String = "D:\goo\python\goo_高齢者支援\Wariate.py"
    Const infile As String = "D:\goo\python\goo_高齢者支援\INPUT.csv"
    Const outfile As String = "D:\goo\python\goo_高齢者支援\OUTPUT.csv"
    Dim ws1 As Worksheet
    Dim ws2 As Worksheet
    Dim maxrow As Long
    Dim maxcol As Long
    Dim wrow As Long
    Dim wcol As Long
    Set ws1 = Worksheets("高齢者支援")
    Set ws2 = Worksheets("実行結果")
    maxrow = ws1.Cells(rows.Count, 1).End(xlUp).Row
    maxcol = ws1.Cells(1, Columns.Count).End(xlToLeft).Column
    If maxrow < 4 Then Exit Sub
    If maxcol < 4 Then Exit Sub
    ws1.Range(ws1.Cells(1, 1), ws1.Cells(maxrow, maxcol)).Interior.Pattern = xlNone
    
    '入力ファイル作成
    Open infile For Output As #1
    For wrow = 2 To maxrow
        Dim oline As String
        oline = ws1.Cells(wrow, 2).Value
        For wcol = 3 To maxcol
            oline = oline & "," & ws1.Cells(wrow, wcol).Value
        Next
        Print #1, oline
    Next
    Close #1
    'Python 実行
    Dim WSH, wExec, sCmd As String, result As String, ResultERR As String
    Set WSH = CreateObject("WScript.Shell")
    sCmd = "python " & pyscript & " " & infile & " " & outfile
    Set wExec = WSH.Exec("%ComSpec% /c " & sCmd)
    Do While wExec.Status = 0
        DoEvents
    Loop
    result = wExec.StdOut.ReadAll
    If result <> "" Then
        MsgBox result
    Else
        MsgBox ("スクリプト実行エラー")
        ResultERR = wExec.StdErr.ReadAll
        MsgBox (ResultERR)
        Exit Sub
    End If
    '実行結果設定
    Call set_result(ws1, ws2, result, outfile)
    MsgBox ("完了")
End Sub
Private Sub set_result(ByVal ws1 As Worksheet, ByVal ws2 As Worksheet, ByVal result As String, ByVal fpath As String)
    Dim maxrow As Long
    Dim wrow As Long
    Dim sline As String
    Dim elm As Variant
    Dim row1 As Long
    Dim col1 As Long
    Dim minsum As Long: minsum = 0
    Dim maxsum As Long: maxsum = 0
    If result = "" Then Exit Sub
    If Left(result, 9) <> "STATUS=OK" Then Exit Sub
    Set ws2 = Worksheets("実行結果")
    maxrow = ws2.Cells(rows.Count, "A").End(xlUp).Row
    If maxrow > 2 Then
        ws2.Range("A3:J" & maxrow).ClearContents
    End If
    Open fpath For Input As #2
    wrow = 3
    Do Until EOF(2)
        Line Input #2, sline
        elm = Split(sline, ",")
        row1 = elm(0) + 2
        col1 = elm(1) + 2
        ws1.Cells(row1, col1).Interior.Color = 5296274  '緑
        ws2.Cells(wrow, "A").Value = ws1.Cells(row1, 1).Value
        ws2.Cells(wrow, "B").Value = ws1.Cells(1, col1).Value
        ws2.Cells(wrow, "C").Value = elm(0)
        ws2.Cells(wrow, "D").Value = elm(1)
        ws2.Cells(wrow, "E").Value = elm(2)
        row1 = elm(3) + 2
        col1 = elm(4) + 2
        If ws1.Cells(row1, col1).Interior.Color <> 5296274 Then
            '未設定なら黄
            ws1.Cells(row1, col1).Interior.Color = 65535
        Else
            '緑設定済みなら赤
            ws1.Cells(row1, col1).Interior.Color = 255
        End If
        ws2.Cells(wrow, "F").Value = ws1.Cells(row1, 1).Value
        ws2.Cells(wrow, "G").Value = ws1.Cells(1, col1).Value
        ws2.Cells(wrow, "H").Value = elm(3)
        ws2.Cells(wrow, "I").Value = elm(4)
        ws2.Cells(wrow, "J").Value = elm(5)
        minsum = minsum + elm(2)
        maxsum = maxsum + elm(5)
        wrow = wrow + 1
    Loop
    Close #2
    ws2.Cells(wrow, "A").Value = "合計"
    ws2.Cells(wrow, "E").Value = minsum
    ws2.Cells(wrow, "J").Value = maxsum
End Sub

高齢者支援のシート（あなたが提示したシートと同じ）
実行結果のシート

Comments

[nudru]

2番のところをスクリプトやcsvがある私のファイルのパスに変更し、「高齢者支援」のシートに最初私が出していた画像のように距離行列を書き、VBAを実行しました。他のところも行いました。
すると、指定したファイルのパスに「INPUT.csv」が保存されましたが、スクリプト実行エラーと表示され、画面の真ん中に色々書かれた小さい画面が表示されました。

[tatsu99]

そのエラーの内容を提示することは、可能でしょうか。
それが、難しいなら、idleから直接、Wariate.pyを起動してください。
その場合は、パラメータとして INPUT.csv OUTPUT.csv
と入力してください。（INPUT.csvとOUTPUT.csvの間は空白を入れてください）
その結果のメッセージを表示してください。

[nudru]

valueerror:could not convert string ''to int32 at row 0, column 433.
とでました

[nudru]

上のはVBAを実行した際のエラーです。
今からidleの方で行います

[nudru]

idleで行いましたが、同じエラーが起こりました。

[tatsu99]

CSVファイルの値に数値に変換できないものがあるといってます。
excelの2行目の435列の値が不正です。
excelの1行目の見出しに、＜ー支援者がいる住宅
1列目の見出しに、↑高齢者がいる住宅
がありますが、それは、削除してください。
実際の住宅番号が書かれている、行、列までを扱うようにしています。
＜ー支援者がいる住宅、↑高齢者がいる住宅があると、正しいサイズがはあくできなくなります。

[nudru]

返信も早いですし、とても困っていたので大変助かりました！
本当にありがとうございました！！

[nudru]

以前、距離の総和の最小と最大それぞれの場合の支援者と高齢者のいる住宅番号の組み合わせをだすVBAのコードを教えていただいたのですが、
支援者と高齢者のいる住宅番号をミニマックス法で組みあわせ、結果を以前のように算出したいです。このコードを教えて頂きたいのですがよろしいでしょうか。

[tatsu99]

>支援者と高齢者のいる住宅番号をミニマックス法で組みあわせ、結果を以前のように算出したいです。

申し訳ありませんが、私はミニマックス法について知りませんので、回答できません。
私への質問ではなく、新たな、ミニマックス法の質問として、スレッドをたてていただければ、良い回答が得られやすくなるかと思います。

[nudru]

ミニマックス法とは、各組み合わせの距離の最大値をできるだけ小さくしたものを言います。
追加した画像で説明します。左の組み合わせがMin Sumで右がMin Max法です。
合計距離は左の方が小さいのですが、それぞれでの組み合わせの距離の最大値ができるだけ小さくしたものが右の組み合わせとなります。
結果が Min SumよりもMin Maxの方が距離が長かったり、 Min Maxが Min Sumとなる場合もあります。

[tatsu99]

よくわかりません。
提示されたMin sum と Min Maxの値の画像は、その上の画像と関係あるのでしょうか。
あるとすれば、高齢者の住宅番号が、Min Sumは2,3,4,6ですが上の画像は1,1,3,5なので合っていません。

提示されたMin sum と Min Maxの値の画像がその上の画像と関係ないならば、
その上の画像に該当するものを提示していただけませんでしょうか。
そのうえで、Min SumとMin Maxをどうやって算出しているのかを説明していただけませんでしょうか。

[nudru]

どちらも変更致しました。要支援者→高齢者
上の画像が行列で、緑にマークされたところが前回教えていただいた Min Sum（総和の最短距離）となる部分です。

以下Min Maxの説明

組み合わせの各距離の最大値を最小にしつつ、その中でできるだけ総距離も短くなるように組み合わせます。
今回ではその結果が下の画像の右のようになります。

このとき距離の最大値が20となるのですが、この20は他の組み合わせを行った時の最大値の中で最小の値となり、その中でもこの3組の総距離が最短となるため、今回のような組み合わせとなります。

そのため、総距離は距離行列によってはMin Sumよりも小さくなる可能性もありますし、大きくなる可能性もあります。
今回では Min Sumよりも総距離が長くなっていますが、各距離の最大値は1番小さい20となっております。

[tatsu99]

Min Maxについて、よくわかりませんでした。私では回答できませんので、他の回答者の回答を待ってください。本スレッドは解決済みになっているので、他の回答者の目に留まりにくくなっています。新たに質問を起こされた方が、回答が得られやすくなるかと思います。お役に立てず、申し訳ありません。

Answer 2

munkresのインストールが正常に終了し、munkresを使用するスクリプトが正常に動作する前提となりますが、
以下のようにしては、いかがでしょうか。
１．シート名：高齢者支援
に高齢者住宅番号と支援者住宅番号、距離を記入する。
２．マクロを実行すると、
上記シートの距離の箇所をCSVファイルに出力する。（B2:F5の範囲）
３．マクロからpythonを実行し、最短距離と最長距離を算出する。
算出結果を別のCSVファイルへ出力する。
４．マクロは、算出結果が書かれたCSVファイルを読み込み、
シート名：算出結果へ出力する。
同時に、シート名：高齢者支援に最短距離と最長距離を色づけする。
上記で良ければ、マクロとpythonスクリプトを提供可能です。

Comments

[nudru]

ありがとうございます。
200×200ほどだと時間はどのぐらいかかるかわかりますか？
1日前後ぐらいで終わる場合、それらをいただきたいです。

[tatsu99]

>200×200ほどだと時間はどのぐらいかかるかわかりますか？
こちらで、適当なデータをいれて行ったところ、一瞬でした。なので最悪でも１分程度かと思います。
ちなみに132X431のデータでも、１０秒程度で終わりました。
まずは、私が最初に投稿したスクリプト（投稿2023/11/12 19:36）で、期待した結果が表示される
ことを確認して下さい。

[nudru]

ありがとうございます！！
できました！

Answer 3

windowsのコマンドプロンプトです。

windowsシステムツールを開くと
コマンドプロンプトがあるので、それをクリックしてください。
その画面で
pip install munkres
と入力してください。
そうするとmunkresのインストールが始まります。

Comments

[tatsu99]

すみません。画像を見るとコマンドプロンプトで実行されていますね。
行き違いがあったようです。失礼しました。

Answer 4

コマンドプロンプトでpip install munkresと打つと、
File "<stdin>",line 1
pip install munkresとでて、installのしたに波線がでます。

コマンドプロンプトとは、以下のような画面ですが、まちがいないでしょうか。

私の場合は、インストール済みなので、その旨のエラーメッセージが表示されますが、
少なくとも、波線は表示されないはずです。

Comments

[nudru]

はい
別のパソコンで行うとできたのですが、
import csvからが表示した画像のようになりました。

[tatsu99]

>import csvからが表示した画像のようになりました。
これは、コマンドプロンプトから打つ必要はありません。
コマンドプロンプト スクリプトを格納したフォルダに移動します。
cd 移動したフォルダ名　
で移動できます。
dir
と入力すると、ファイル一覧が表示されます。
スクリプトファイルと処理したいCSVファイルがあることを確認してください。
python スクリプトファイル CSVファイル　
と入力すると実行します。
例
python Hungarian.py sample.csv

[nudru]

いただいたコードで実行すると、
===== RESTART: pyファイルのパス=====
pyファイルのパス P1
P1:csvファイルのパス
となり、
pyファイルのパス P1は青文字、
P1:csvファイルのパスは赤文字で表示されました。

[tatsu99]

idleから実行するとき
Run->Run Module(F5)
で実行されたように見えます。
CSVファイル名が指定されていないので、そのようなメッセージが表示されます。
Run->Run ...Customized(Shift+F5)
で実行してください。
そうすると、パラメータを打ち込む画面が表示されるので、CSVファイル名を入力してください。
例 sample.csv
CSVファイルは、スクリプトと同じフォルダに格納してください。
そうすると、期待した結果が表示されるかと思います。

Answer 5

URLにハンガリアン法のコードはあります。

とは 割当問題のハンガリアン法をpythonで実装してみた の「python による実装」のコードと解釈しました。これを用いる手順としては以下になります。

• このコードを qiita_hungarian.py という名前のファイルに保存し，カレントディレクトリ（フォルダ）に置きます。

• このコードは正方行列でないと正解が得られない場合があるようなので，CSV ファイル（sample.csv とします）の6行目にダミー行「x,0,0,0,0,0」を追加して，同じディレクトリに置きます。

• 下記の記述例をファイル（例えば code1.py）に保存し，同じディレクトリに置きます。そして，実行（例えば > python code1.py）します。

なお，「最大の割当」を求める際は，与える距離データの符号を負にしてから「最小の割当」を求めました。総当たり法（Brute-force method）の結果とは一致しましたが，（qiita_hungarian.py のコードの中身をよく理解できていないので）この方法が正しいとまでは言えません。

import pandas as pd
from qiita_hungarian import Hungarian
from itertools import permutations

df = pd.read_csv('sample.csv', index_col=0)
print(df)
#     1   2   3   4   5
# 1   0  10  30  40  50
# 1   0  10  30  40  50
# 3  30  15   0  20  25
# 5  50  35  25  15   0
# x   0   0   0   0   0

for k in (1, -1):
    h = Hungarian()
    result = h.compute(df.to_numpy() * k)
    distance = sum(df.iloc[t] for t in result)
    pairing = [(df.index[i], df.columns[j]) for i, j in result
               if df.index[i] != 'x']
    print('min:' if k == 1 else 'max:', distance, pairing)
# min: 10 [('1', '1'), ('1', '2'), ('3', '3'), ('5', '5')]
# max: 155 [('1', '4'), ('1', '5'), ('3', '1'), ('5', '2')]

# Brute-force method
sum_lst = [sum(df.iloc[t] for t in zip(range(5), p))
           for p in permutations(range(5))]
print(f'min: {min(sum_lst)}, max: {max(sum_lst)}')
# min: 10, max: 155

Comments

[nudru]

ありがとうございます。
Module Not Found Error: No module named 'pandas'とでました。

[nudru]

コマンドプロントでpandasをインストールした後実行すると、以下のようなエラーとなりました。
ImportError: cannot import name 'Hungarian' from partially initialized module 'qiita_hungarian' (most likely due to a circular import)（pyファイルのパス）

[little_street]

「実行」とは記述例を保存したファイルを仮に code1.py とするとコマンドプロンプトで
> python code1.py
と入力したということでよろしいですか。そうであれば
> dir
と入力して，同じ場所に quiita_hungarian.py と sample.csv が置かれていることを確認ください。

[little_street]

回答の「実行」部分の説明を少し書き加えました。

[nudru]

ありがとうございます！

Answer 6

見出しの部分を除いたCSVファイルであることが、前提です。
提示例ではB2:F5
0,10,30,40,50
0,10,30,40,50
30,15,0,20,25
50,35,25,15,0
のようなCSVファイルです。

import csv
import sys
from munkres import Munkres
import numpy as np
import copy

arr = []
if len(sys.argv) != 2:
    print(sys.argv[0],"P1")
    print("P1:CSVファイル名",file=sys.stderr)
    sys.exit(1)
fin = open(sys.argv[1], "r")
work = csv.reader(fin)

for work_l in work:
    work_n = list(map(lambda x: int(x),work_l))
    arr.append(work_n)
fin.close()

mtx = np.array(arr)
ansMtx = Munkres().compute(copy.copy(mtx))
asum = sum([mtx[idx] for idx in ansMtx])
print(mtx)
print(ansMtx)
print(f"Minmum sum = {asum}")

上記で最小値は求められます。
最大値の求め方は不明です。
Usage:
python.exe スクリプトファイル CSVファイル

Comments

[nudru]

ありがとうございます。
コマンドプラントでpip install munkresと打ち、idleの方でいただいたコードで打ちました。
すると以下のようなエラーが起こったのですがどのようにすればよろしいでしょうか。

Traceback (most recent call last):
File "ファイル名/test.py", line 3, in <module>
from munkres import Munkres
File "ファイル名\munkres.py", line 1
pip install munkres
^^^^^^^
SyntaxError: invalid syntax

[tatsu99]

munkres.pyというファイルを作成されましたでしょうか？
munkres.pyの1行目が
pip install munkres
になっているように見えます。
私が提示したスクリプトのファイル名は、test.pyでしょうか。
OSは何でしょうか。当方はwindows10のコマンドプロンプトから起動して確認しています。

[tatsu99]

もし、”ファイル名”というフォルダのなかにmunkres.pyがあるなら、それが原因です。
from munkres import Munkresの行で
munkres.pyを探して、そのファイルを読み込んでいます。
そのファイルをリネームするか、他の場所に移動するかして、読み込まないようして下さい。

[nudru]

ファイル名→csvファイルのパスでした。
スクリプトのファイル名をmunkres.pyに変更し、それをidleで実行しました。
1行目にpip install munkresをいれると、there's an error in your program:invalid syntaxとでて、installの部分が赤くなります。

1行目をpipのやつを入れずに、import csvから始めると、同じようなエラーがでて、
print("P1:csvファイルのパス",file=sys.stderrのsysの後ろの.が赤くなります。

[nudru]

windows10を使用しております。
Python2.7.8です

[tatsu99]

munkres.pyというファイルを作成してはいけません。
munkres.pyというファイルは、pip install munkresを行うと、自動的にpythonのライブラリとして作成されます。
スクリプトファイル名は、他の名前にしてください。
例　Hungarian.py　等

[tatsu99]

>Python2.7.8です
これは、古すぎます。こちらは、Python 3.11.3で確認しています。
せめてpython3にしていただけませんでしょうか。
Python2では動作しないと思われます。

[nudru]

スクリプトファイル名を変更しましたが、同じようなエラーとなりました

[nudru]

今から更新致します

[tatsu99]

＞スクリプトファイル名を変更しましたが、同じようなエラーとなりました
コマンドプロンプトで、実行していただけませんでしょうか。
そして、打ち込んだコマンドと実行結果（エラーメッセージ）を提示していただけませんでしょうか。
但し、python2.7.8では、エラーになるとおもいますので、python3で実行した結果を
提示していただけませんでしょうか。

[nudru]

更新しました。
1行目にpip install munkresを入れた時は、invalid syntaxとなってinstallのiが赤くなりました。

import csvから始めた時は、
Modle Not Found Error: No module named'munkres'となりました。

スクリプトファイル名は変更しております。

[nudru]

承知しました。

[nudru]

コマンドプロンプトでpip install munkresと打つと、
File "<stdin>",line 1
pip install munkresとでて、installのしたに波線がでます。

[tatsu99]

>コマンドプロンプトでpip install munkresと打つと、
python ２はアンインストール完了
python 3はインストール完了
の状態で実行されましたでしょうか。
コマンドプロンプトについて、齟齬があるような気がします。回答を参照してください。
あなたのいっているコマンドプロンプトは、どうやって起動されましたでしょうか。

これから１時間ほど外出します。