このページは福井県立大学の田中求之が2006年1月まで運用していた Mac のサーバ運用に関する会議室 「Web Scripter's Meeting」の記録です。情報が古くなっている可能性がありますのでご注意ください。

最適割り当てを解く事が可能でしょうか

発言者:しんいち
( Date Saturday, September 04, 2004 18:43:41 )


AppleScriptで最適割り当てがハンガリー法を用いて
解く事が可能でしょうか?
もし挑戦された方がありましたら何かアドバイスが
あれば、お聞かせください。

福岡3285 さんからのコメント
( Sunday, September 05, 2004 14:46:49 )

無理でしょう。
C++やジャバでは可能です
4*4ならJavaScriptでも出来ますよ

福岡3285 さんからのコメント
( Saturday, July 02, 2005 15:27:05 )

やっと出来ました。
JavaScriptで最適割り当てをハンガリー法を用いて解く事が出来ました。
行列4*4ならわりと早く結果を表示出来るのですが、
それ以上だと、かなりの時間が必要で実用的ではありません。
参考になればと以下に書きます。

ご意見がありましたらお聞かせ下さい。

<HTML><HEAD>
<TITLE>ハンガリー法</TITLE>

<SCRIPT LANGUAGE="JavaScript">
m=-1;kou1=0;kou2=0;mm=0;nai=0;a=0;b=0;c=0;d=0;e=0;
X=new Array();

sinX=new Array();
neoX=new Array();
Y=new Array();
sinY=new Array();
syo=new Array();
xy=new Array();
Out=new Array();

for(i=0;i<4;i++){
sinX[i]=new Array();
neoX[i]=new Array();
Y[i]=new Array();
sinY[i]=new Array();
X[i]=new Array();
}

for(i=0;i<6;i++){
xy[i]=new Array();
}

Nrr = new Array("A","B","C","D");
Krr = new Array("","1","2","3","4");
KLn = Krr.length;
NLn = Nrr.length;
Tex = new Array();//text box

function main(){
  if(numCheck()) {
    alert("数値以外が含まれています");
    return;
  }
  if(nonCheck()){
                alert("すべての欄に入力してください");
                return;
  }

  for(j=0;j<4;j++){
    for(i=0;i<4;i++){
      X[j][i]= eval(GetTextValue("Lay1",Tex[j][i]));
                }
        }
zero();
siraberu();
end();
  for(i=0;i<4;i++){
  for(j=0;j<4;j++) FormTextChange("Lay2",Tex[i][j],neoX[i][j])
  }
Lay2.style.visibility="visible";
ans.innerText = kekka;
saiteki.style.visibility="visible";
ans.style.visibility="visible";
}


function zero(){
for(j=0;j<4;j++){
syo1=0;syo2=0;syo3=0;
   syo1=Math.min(X[j][0],X[j][1]);
   syo2=Math.min(X[j][2],X[j][3]);
   syo3=Math.min(syo1,syo2);
     for(i=0;i<4;i++){
     sinX[j][i]=X[j][i]-syo3;
     }
}
//二回目
for(j=0;j<4;j++){
syo1=0;syo2=0;syo3=0;
   syo1=Math.min(sinX[0][j],sinX[1][j]);
   syo2=Math.min(sinX[2][j],sinX[3][j]);
   syo3=Math.min(syo1,syo2);
     for(i=0;i<4;i++){
     neoX[i][j]=sinX[i][j]-syo3;
     }
}
}

function siraberu(){
 for(a=0;a<4;a++){
  for(b=1;b<5;b++){
     while(a>=b&&b<4){b++;}
   for(c=2;c<6;c++){
      while(b>=c&&c<5){c++;}
    for(d=3;d<7;d++){
        while(c>=d&&d<6){d++;}
     for(e=4;e<8;e++){
        while(d>=e&&e<7){e++;}
     A=a;E=e-4;xy[5]=neoX[A][E];
       if(b>3){
       B=b-4;C=c-4;D=d-4;
       xy[0]=neoX[A][B];xy[1]=neoX[A][C];xy[2]=neoX[A][D];
          if(xy[0]!=0&&xy[1]!=0&&xy[2]!=0&&xy[5]!=0){
          zero();
          check();
          }
       }else if(b<=3&&c>3){
       B=b;C=c-4;D=d-4;
       xy[0]=neoX[A][C];xy[1]=neoX[A][D];xy[2]=neoX[B][C];xy[3]=neoX[B][D];xy[4]=neoX[B][E];
          if(xy[0]!=0&&xy[1]!=0&&xy[2]!=0&&xy[3]!=0&&xy[4]!=0&&xy[5]!=0){
          kousa();
          neoX[A][E]-=mm;neoX[A][C]-=mm;neoX[A][D]-=mm;
          neoX[B][E]-=mm;neoX[B][C]-=mm;neoX[B][D]-=mm;
          check();
          }
       }else if(c<=3&&d>3){
       B=b;C=c;D=d-4;
       xy[0]=neoX[A][D];xy[1]=neoX[B][D];xy[2]=neoX[B][E];xy[3]=neoX[C][D];xy[4]=neoX[C][E];
          if(xy[0]!=0&&xy[1]!=0&&xy[2]!=0&&xy[3]!=0&&xy[4]!=0&&xy[5]!=0){
          kousa();
          neoX[A][E]-=mm;neoX[A][D]-=mm;neoX[B][D]-=mm;
          neoX[B][E]-=mm;neoX[C][D]-=mm;neoX[C][E]-=mm;
          check();
          }
       }else if(d<=3){
       B=b;C=c;D=d;
       xy[0]=neoX[B][E];xy[1]=neoX[C][E];xy[2]=neoX[D][E];
          if(xy[0]!=0&&xy[1]!=0&&xy[2]!=0&&xy[5]!=0){
          zero();
          check();
          }
       }
     }
    }
   }

  }
 }
}

function kousa(){
        mm=xy[0];
        for(i=1;i<6;i++){
              if(mm>xy[i]){
              mm=xy[i];
              }
        }
Arr=new Array(0,1,2,3,4,5,6,7);
        Out[0]=a;Out[1]=b;Out[2]=c;Out[3]=d;Out[4]=e;
  for(i=0;i<Out.length;i++) Out[i] = eval(Out[i])
  for(i=0;i<Out.length;i++){
    Arr0 = Arr.slice(0,Out[i])
    Arr1 = Arr.slice(Out[i]+1,Arr.length)
    Arr = Arr0.concat(Arr1)
    if(Out[i+1]) Out[i+1] -= i+1
  }

        AA=Arr[0];bb=Arr[1];cc=Arr[2]-4;
        neoX[AA][cc]+=mm;
        if(bb<4){
        neoX[bb][cc]+=mm;
        }else if(bb>3){
        BB=bb-4;
        neoX[AA][BB]+=mm;
        }
        
}

function check(){
for(i=0;i<4;i++){
   for(j=0;j<4;j++){
     X[i][j]=neoX[i][j];
   }
}
siraberu();
}


function end(){
 
for(a=1;a<5;a++){
   for(b=1;b<5;b++){
     for(c=1;c<5;c++){
       for(d=1;d<5;d++){
         if(a*b*c*d==24&&a+b+c+d==10){
           if(neoX[0][a-1]+neoX[1][b-1]+neoX[2][c-1]+neoX[3][d-1]==0){
kekka="A-"+a+" B-"+b+" C-"+c+" D-"+d;
            }
         }
       }
    }
   }
}
}




//---------------------------------------------●表書き出し
function tableWrite(){
  Str = '<div id="Lay1">'
  Str += '数字を入力して、開始ボタンを押してください'
  Str += '<form name="form1" onsubmit="return false">'
  Str += '<table border=1 cellpadding=0 cellspacing=0>'
  Str += '<tr>'
  for(k=0;k<KLn;k++){ //項目
    Str += '<td align="center" bgcolor="#dddddd">'+Krr[k]+ '</td>'
  }
  Str += '</tr>'
  for(j=0;j<NLn;j++){
    Tex[j] = new Array()
    Str += '<tr>'
    Str += '<td align="center" bgcolor="#dddddd">&nbsp;'+Nrr[j]+'&nbsp;</td>'
    for(i=0;i<KLn-1;i++){
      Tex[j][i] = "text"+j+i
      Str += '<td width=20>'
      if(j==NLn-1 && i==KLn-1) Str += '&nbsp;'
      else Str += '<input type="text" name='+Tex[j][i]+' size="6" Value='+(j+1)*(i+1)*10+'>'
      Str += '</td>'
    }
    Str += '</tr>'
  }
  Str += '</table> <br>'
  Str += '<input type="button" value="&nbsp;開始&nbsp;" onClick="main()"> '
  Str += '<input type="reset" value="&nbsp;Reset&nbsp;">'
  Str += '</form>'
  Str += '</div>'

  Str += '<div id="Lay2">'
  Str += '<font color="ff0000">答え</font>'
  Str += '<form name="form2" onsubmit="return false">'
  Str += '<table border=1 cellpadding=0 cellspacing=0>'
  Str += '<tr>'
  for(k=0;k<KLn;k++){ //項目
    Str += '<td align="center" bgcolor="#dddddd">'+Krr[k]+ '</td>'
  }
  Str += '</tr>'
  for(j=0;j<NLn;j++){
    Tex[j] = new Array()
    Str += '<tr>'
    Str += '<td align="center" bgcolor="#dddddd">&nbsp;'+Nrr[j]+'&nbsp;</td>'
    for(i=0;i<KLn-1;i++){
      Tex[j][i] = "text"+j+i
      Str += '<td width=20>'
      if(j==NLn-1 && i==KLn-1) Str += '&nbsp;'
      else Str += '<input type="text" name='+Tex[j][i]+' size="6">'
      Str += '</td>'
    }
    Str += '</tr>'
  }
  Str += '</table> <br>'
  Str += '</form>'
  Str += '</div>'
  document.write(Str)
}


//---------------------------------------------●入力チェック
function numCheck(){
  for(j=0;j<4;j++){ //入力部分のみチェック
    for(i=0;i<4;i++){
      txt = GetTextValue("Lay1",Tex[j][i])
      data = txt.match(/[^0-9]/g) //数字以外
      if(data) return true
    }
  }
  return false
}
function nonCheck(){
  for(j=0;j<4;j++){ //入力部分のみチェック
    for(i=0;i<4;i++){
      txt = GetTextValue("Lay1",Tex[j][i])
      if(txt=="") return true
    }
  }
  return false
}



//---------------------------------------------●レイヤー内のform text value
function GetTextValue(Lay,Name) { //form name--form1
  if(document.layers) 
    Str = document.layers[Lay].document.form1.elements[Name].value
  else if(document.all || document.getElementById) 
    Str = document.form1.elements[Name].value
  return Str
}

//---------------------------------------------●レイヤー内のform textチェンジ
function FormTextChange(Lay,Name,Str) { //form name--form1
  if(document.layers) 
    document.layers[Lay].document.form2.elements[Name].value = Str
  else if(document.all || document.getElementById) 
    document.form2.elements[Name].value = Str
}

//---------------------------------------------●for Netscape
function NcReload(){window.document.location.reload()}
if(document.layers) window.onresize = NcReload

//-->
</script>

<style type="text/css"><!--

.f12,td,input{ font-size:12px; color:black }
.f10{ font-size:10px; line-height:16px; width:380px; color:black }

body{ background:#ffffff; margin:0 0 0 0 }
A{ TEXT-DECORATION: none; font-weight:bold}
A:LINK{ COLOR: blue }
A:HOVER{ COLOR: orange }
A:ACTIVE{ COLOR: red }
A:VISITED{ COLOR: gray }

#Lay1{ position:absolute; left:30px; top:30px; z-index:1;visibility : visible; }
#Lay2{ position:absolute; left:30px; top:250px; z-index:2;visibility : hidden; }
#ans{ position:absolute; left:30px; top:450px; z-index:2;visibility : hidden; }
#saiteki{ position:absolute; left:30px; top:420px; z-index:2;visibility : hidden; }
//--></style>

</HEAD>
<BODY >

<script language="JavaScript">
<!--
tableWrite()
//-->
</script>
<div id="saiteki">最適な組み合わせは</div>
<div id="ans"></div>
</BODY>
</html>