In: Genel


2022-02-25Yorumlar

Önceki makalede Python’un
yığınq modülü, standart Python’un, sıralama ile ilgili olduğunu düşünebildiğim, ancak sıralama düzeni üzerinde tam kontrol sağlamayan tek parçasıdır.

Bu, öncelik sırası olarak bir heapq kullanırken dikkatli olmanız gerektiği anlamına gelir.

Örneğin, A* arama algoritması bir
en iyisi ilk yol bulucu Bu adımlardan geçen yolun toplam mesafesinin tahmini tarafından sıralanan, atılacak olası adımların bir öncelik sırası tutar. Her aşamada, kuyruktan bir sonraki adımı – en kısa tahmini toplam mesafeye sahip olanı – açar ve ardından yeni konuma göre güncellemeler yapar.

import heapq

def a_star(start, heuristic, moves):
    """A* graph search

    - start: initial state
    - heuristic(s): estimates path length from state s to finish. 
                    heuristic(s) == 0 => finished
    - moves(s): neighbours of s

    Returns the shortest path to the finish and its cost, on success.
    None otherwise.
    """
    costs = {start: 0}
    prev = {start: None}
    frontier = [(heuristic(start), start)]
    heapq.heapify(frontier)

    def path(s):
        return [] if s is None else path(prev[s]) + [s]

    while frontier:
        priority, state = heapq.heappop(frontier)
        if heuristic(state) == 0:
            return costs[state], path(state)
        for n in moves(state):
            n_cost = costs[state] + 1
            if n not in costs or n_cost < costs[n]:
                costs[n] = n_cost
                heapq.heappush(frontier, (n_cost + heuristic(n), n))
                prev[n] = state

Yukarıdaki kod bir Python A* uygulamasıdır. Basit olması için, her adımın maliyetinin 1 olduğunu varsayacağız. Durum bu değilse, işlevi uyarlamak yeterince kolaydır.

Buradaki öncelik kuyruğunun adı frontier, keşfetmemiz gereken durumların toplamı. Sekans heapify, heappop, heappush
öncelik sırasını korur. (çağrı heapify tek elemanlı bir liste zaten bir yığın olduğundan gerekli bile değildir.) Dolayısıyla, kuyruktan bir durumu her açtığımızda, tahmini maliyeti en düşük olanı alırız. Ardından, bu yeni adımdan yapabileceğimiz hamlelere dayanarak, dahili maliyet kayıtlarımızı ve önceki düğümlerimizi güncelleriz.

Kuyruktaki öğelerin (cost, state) çiftler. Maliyetler sayılar, tipik olarak pozitif tam sayılar olacaktır – kesin değerler buluşsal fonksiyona bağlıdır.

Tam olarak ne olarak kullanılır state sağlayan arayan kişiye bağlıdır startbaşlangıç ​​durumu ve movesbir devletten komşularına adım atan.

Ancak, sıradaki öğeler bağlıysa costheapq’nin karşılaştırması gerekebilir state değerler. Durumların tanımlanmış bir sıralaması yoksa, bu bir çalışma zamanı hatasıyla sonuçlanır.

>>> class State: pass
... 
>>> x1, x2 = State(), State()
>>> (1, x1) < (2, x2)
True
>>> (1, x1) < (1, x2)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'State' and 'State'

için bir sıralama anahtarı sağlayamıyoruz. heapq fonksiyonlar. Bu, istemcilerin durum nesnelerinin – gerçekte her ne iseler – karşılaştırılabilmelerini sağlamaları gerektiği anlamına mı geliyor? Kodun olduğu gibi, evet, ancak modül belgeleri bu durumu ele alma konusunda tavsiyesi var:

[…] girişleri öncelik, giriş sayısı ve görev dahil olmak üzere 3 öğeli liste olarak depolayın. Giriş sayısı, aynı önceliğe sahip iki görevin eklendikleri sıraya göre döndürülmesi için bir bağlayıcı görevi görür. Ve hiçbir giriş sayısı aynı olmadığından, grup karşılaştırması hiçbir zaman iki görevi doğrudan karşılaştırmaya çalışmayacaktır.

Bu strateji daha kullanışlı a_star.

import heapq
import itertools

def a_star(start, heuristic, moves):
    costs = {start: 0}
    prev = {start: None}
    seq = itertools.count().__next__
    frontier = [(heuristic(start), seq(), start)]

    def path(s):
        return [] if s is None else path(prev[s]) + [s]

    while frontier:
        _, _, state = heapq.heappop(frontier)
        if heuristic(state) == 0:
            return costs[state], path(state)
        for n in moves(state):
            n_cost = costs[state] + 1
            if n not in costs or n_cost < costs[n]:
                costs[n] = n_cost
                heapq.heappush(frontier, (n_cost + heuristic(n), seq(), n))
                prev[n] = state

Bir cevap yazın

Ready to Grow Your Business?

We Serve our Clients’ Best Interests with the Best Marketing Solutions. Find out More

How Can We Help You?

Need to bounce off ideas for an upcoming project or digital campaign? Looking to transform your business with the implementation of full potential digital marketing?

For any career inquiries, please visit our careers page here.
[contact-form-7 404 "Bulunamadı"]