0

Pythonを勉強して間もない者です。参考書やネット等で調べたのですが、理解が及ばなかった為、こちらで質問させていただきます。

このプログラムは初期値(V,E)を元に関数IDISTで計算した値を、default_valueとしています。またV=(0,1,2,3,4)を置換したものをpi[]とし120通りの置換したpi[]を元に、新たにnew_Eというエッジを作成し、置換した一つ一つのVを元に、関数IDISTでnew_Eを計算しています。計算したnew_EのIDISTとdefault_valueの値を比較し、小さい方を出力するというのがこのプログラムです。

このプログラムの出力結果として

(0,1,2,3,4)
 12
(0,1,2,4,3)
 10
(0,1,3,4,2)
 11

と全通り出力されていくのですが、私はこのプログラムを120通りの中でIDISTが最も最小なものと、その時の置換pi[]のみを出力したいのです。ですがそのようにする上手い方法が思いつきません。拙い文章ではありますが、どなたかアドバイスを頂けたら幸いです。

目標となる出力

最小コスト 2
その時の置換 (1,4,0,3,2)
       (1,4,2,0,3)
       (1,4,2,3,0)
       (2,0,1,4,3)
       (2,0,3,1,4)
       (2,0,3,4,1)

ソースコード

class Edge():
    def __init__(self,a,b,c):
        self.u = a
        self.v = b
        self.weight = c
    def __str__(self):
        return '(' + str(self.u) + ',' + str(self.v) + ',' + str(self.weight) + ')'

class Graph():
    def __init__(self,d,e):
        self.V = d
        self.E = e

import itertools

V = tuple(range(0, 5)) # tuple of integers
E = (Edge(0,3,1), Edge(0,2,3), Edge(0,4,2), Edge(2,4,1))
G = Graph(V, E)

def iDist(V,E):
    value = 0
    for e in E:
        value += e.weight * abs(abs(e.u - e.v)-1)
    return value

default_value = iDist(V,E)
min_sum = []

for pi in itertools.permutations(V):
    new_E =  (Edge(pi[0],pi[3],1), Edge(pi[0],pi[2],3), Edge(pi[0],pi[4],2), Edge(pi[2],pi[4],1))
    min_sum = min(default_value, iDist(pi,new_E))
    print(pi)
    print(min_sum)
3
  • 1
    プログラミングとはプログラムを作成する行為の名前であり、モノの名前ではありません。
    – htb
    Commented 2019年12月11日 5:17
  • 本文の「プログラミング」表記は私が「プログラム」に書き換えてしまいました。 / @sato さん、始めたばかりで中々難しいかと思いますが、質問のタイトルはもう少し具体的に書いてもらった方が注目してもらいやすくなります。(解決したい問題は何なのか、を説明していると良いです) / 書き方は ヘルプ も参考にしてみてください。
    – cubick
    Commented 2019年12月11日 5:28
  • ややこしい書き方をしてしまい申し訳ありません。。。親切にして頂きありがとうございます。
    – sato
    Commented 2019年12月11日 5:47

1 件の回答 1

1

現状は for 文の中に print(min_sum) が入っているため、すべての繰り返しで出力されてしまっています。最小値は繰り返しきった後に確定するため、for の外側に出す必要があります。

for pi in itertools.permutations(V):
    (... コード ...)
print(min_sum)  # インデントを下げて for の外に出す。

また、出力したいのは「最小値とそのときの pi」なので、min_sum の他に min_pi も覚えておく必要があります。そうするためには最小値を min 関数で求めるのではなく if 文で分岐させる形にすると良いです。

for pi in itertools.permutations(V):
    new_E =  (Edge(pi[0],pi[3],1), Edge(pi[0],pi[2],3), Edge(pi[0],pi[4],2), Edge(pi[2],pi[4],1))
    current_sum = iDist(pi, new_E)
    if current_sum < min_sum:
        min_sum = current_sum
        min_pi = pi
print(min_pi)
print(min_sum)

※毎回 default_value と比較してしまっていたバグもこっそり直しています。

なお、これだと最小値をとる pi がひとつしか分かりません。もし最小値をとる pi をすべて求めたいのであればもう少し工夫する必要があります。たとえば:

for pi in itertools.permutations(V):
    new_E =  (Edge(pi[0],pi[3],1), Edge(pi[0],pi[2],3), Edge(pi[0],pi[4],2), Edge(pi[2],pi[4],1))
    current_sum = iDist(pi, new_E)
    if current_sum < min_sum:
        min_sum = current_sum
        min_pis = [pi]
    elif current_sum == min_sum:
        min_pis.append(pi)
print(min_pis)
print(min_sum)
0

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。