0

マンハッタン距離の計算を使用して、python で 8 パズルのさまざまな種類の並べ替えアルゴリズムを試していました。バブルとマージで完了。具体的には、クイックソートを実現しようとしています。

以下のコードは私にエラーを与えます:

TypeError: unsupported operand type(s) for +: 'NoneType' and 'list'

キューは、要素 (現在の状態、親ノード、深さ、パスコスト、manhattanDistance、MisplacedTilesDistance ) を持つ 8 つの Puzzle 状態のノードのリストです。

改善のための指針

def quickSort(queue, length):
    less = []
    pivotList = []
    more = []
    returnList = []
    if length <= 1:
        return queue
    else:
        if queue == []:
            return
        else:    
            pivot = queue[0][3] + queue[0][4]

        for i in queue:

            if i[3]+i[4] < pivot:
                less.append(i)
                print less
                input("yes")
            elif i[3]+i[4] > pivot:
                more.append(i)
            else:
                pivotList.append(i)

        less = quickSort(less, length)
        more = quickSort(more, length)
        #returnList.append(less, pivotList, more)
        return less + pivotList + more
4

2 に答える 2

2 
        if queue == []:
            return

ここに何かを返すのを忘れました。

于 2013-09-22T09:03:31.680 に答える
0

ウィキペディアのようにクイックソート アルゴリズムを実装しようとしていると思います。Python での実装例を次に示します。必要に応じてカスタマイズできます。

def quickSort(queue):
    lengthOfQueue = len(queue)
    if lengthOfQueue <= 1: return queue
    pivotLocation = lengthOfQueue // 2
    pivot, lesser, greater = queue[pivotLocation], [], []
    for i in range(lengthOfQueue):
        if (i == pivotLocation): continue
        if (queue[i] <= pivot): lesser.append(queue[i])
        else: greater.append(queue[i])
    return quickSort(lesser) + [queue[pivotLocation]] + quickSort(greater)

print quickSort([3, 7, 8, 5, 2, 1, 9, 5, 4])

出力

[1, 2, 3, 4, 5, 5, 7, 8, 9]

説明

疑似コード:

  function quicksort('array')
      if length('array') ≤ 1
          return 'array'  // an array of zero or one elements is already sorted
      select and remove a pivot element 'pivot' from 'array'  // see 'Choice of pivot' below
      create empty lists 'less' and 'greater'
      for each 'x' in 'array'
          if 'x' ≤ 'pivot' then append 'x' to 'less'
          else append 'x' to 'greater'
      return concatenate(quicksort('less'), list('pivot'), quicksort('greater')) // two recursive calls

プログラムがこの疑似コードにどのように適合するかを見てみましょう。

len(queue)

これは、キューの長さを見つけるために使用されます。http://docs.python.org/2/library/functions.html#len

長さが 1 以下の場合、キューをそのまま返します。これは、キューが空であるか、要素が 1 つしかないことを意味します。これが再帰の基本条件です。

キューの中間要素である単純なピボットを選択します。したがって、ピボットの位置を次のように見つけます

pivotLocation = lengthOfQueue // 2

次に、pivot 要素を選択し、2 つの空のリスト (小さい方と大きい方) を作成します。

pivot, lesser, greater = queue[pivotLocation], [], []

次に、2 つの配列を作成する必要があります。一方にはピボット以下の要素が含まれ、もう一方にはピボットより大きい要素が含まれます。このループでそれを行います。

for i in range(lengthOfQueue):
    if (i == pivotLocation): continue
    if (queue[i] <= pivot): lesser.append(queue[i])
    else: greater.append(queue[i])

ピボット要素をより少ないまたはより大きなものに送りたくありません。したがって、このようにピボット要素をスキップします。

if (i == pivotLocation): continue

次に、同じアルゴリズムを使用して両方の配列を並べ替え、結果を連結して返します。

return quickSort(lesser) + [queue[pivotLocation]] + quickSort(greater)
于 2013-09-22T09:15:44.247 に答える