or1ko's diary

日々を書きます

2958 Pizza deliveryの続き

2958 Pizza delivery - ori’s diaryの続き
上の記事の最後で,局所解が明らかにあると書いたのだけども,これは間違いだった.いつもの会で,先生が説明してくれたので,それを自分なりに説明してみる.

まず,getCostメソッドを式として書くと以下のようになる.(メモ化の処理は含まない)
getCost(x,y)=\sum_{i=1}^{w} \sum_{j=1}^{h} { C_{ij} (| x - i| + | y - j |)
この式において,各変数の意味は,以下の通り.
 c_{ij} : 座標(i,j)のピザの配達数
 w : 区画の横の長さ
 h : 区画の縦の長さ
この式を変形する.
getCost(x,y)=\sum_{i=1}^{w} \sum_{j=1}^{h} { C_{ij} | x -i | + \sum_{i=1}^{w} \sum_{j=1}^{h} C_{ij} | y - i |
yとxの計算を分離することができた.他の人はこの式を使って,縦と横を分けて解くアルゴリズムでAcceptされていた.局所解を持たないかどうかの話はさらに続き,この式の第1項目に注目する.
\sum_{i=1}^{w} \sum_{j=1}^{h} { C_{ij} | x -i |
この式のシグマの中身である C_{ij} | x - i | は凸関数であり,凸関数は局所解を持たない(修正2/6)凸関数は局所最適解が大域最適解と一致する.さらに,凸関数と凸関数を加算してできた関数は凸関数になることが証明されている.getCost関数の数式は,凸関数の加算のみで構成されいるので,凸関数になり,局所解を待たないということでした.なので,チートコードではありませんでした.

今回の敗因は,メソッドを一度も数式にしなかったことです.以前も数式に直したらアルゴリズムが展開できたことがありました.反省.でも,動的計画法のように解けるのではないかと,そっち方向では式にして考えたのですけどね....単純に数式に対するセンスがないから,こういうことになるのだろうな.


追記
schrodinさんツッコミありがとうございます。修正しました。