Durum alanı - State space

Bu makale genel bir liste içerir Referanslar, ancak büyük ölçüde doğrulanmamış kalır çünkü yeterli karşılık gelmiyor satır içi alıntılar. Lütfen yardım edin geliştirmek bu makale tanıtım daha kesin alıntılar. (2012 Şubat) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin)

Vakum Dünyası, bir en kısa yol problemi sonlu durum uzayı ile

Bir durum alanı bir sistemin tüm olası konfigürasyonlarının kümesidir.^[1] Belirli bir sistemin davranışı hakkında akıl yürütmek için yararlı bir soyutlamadır ve yaygın olarak yapay zeka ve oyun Teorisi.

Örneğin, oyuncak problemi Vakum Dünyası, vakum ve kirin içinde olabileceği sınırlı bir konfigürasyon kümesinin olduğu ayrı bir sonlu durum uzayına sahiptir. Durumların olduğu bir "sayaç" sistemi doğal sayılar 1'den başlar ve zamanla artar^[2] sonsuz bir ayrık durum uzayına sahiptir. Sönümsüzün açısal konumu sarkaç^[3] sürekli (ve dolayısıyla sonsuz) bir durum uzayıdır.

Tanım

Teorisinde dinamik sistemler, bir işlev tarafından tanımlanan ayrı bir sistem ƒ, sistemin durum uzayı yönlendirilmiş olarak modellenebilir grafik Dinamik bir sistemin her olası durumunun bir tepe noktası ile temsil edildiği ve yönlendirilmiş bir kenar olduğu a -e b ancak ve ancak ƒ(a) = b.^[4] Bu bir durum diyagramı.

Bir işlev tarafından tanımlanan sürekli bir dinamik sistem için ƒ, sistemin durum uzayı görüntü nın-nin ƒ.

Durum uzayları, bilgisayar Bilimi basit bir makine modeli olarak. Biçimsel olarak, bir durum uzayı bir demet [N, Bir, S, G] nerede:

• N bir Ayarlamak eyaletlerin
• Bir durumları birbirine bağlayan bir dizi yaydır
• S boş değil alt küme nın-nin N başlangıç ​​durumlarını içeren
• G boş olmayan bir alt kümesidir N hedef durumlarını içeren.

Özellikleri

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Sekiz kraliçe bulmacasının durum uzayında geçerli bir durum

Bir durum uzayının bazı ortak özellikleri vardır:

• karmaşıklık, nerede dallanma faktörü önemli
• mekanın yapısı, ayrıca bakınız grafik teorisi:
  • yayların yönü
  • ağaç
  • köklü grafik

Örneğin, Vakum Dünyası, 4'lük bir dallanma faktörüne sahiptir, çünkü elektrikli süpürge hareket ettikten sonra 4 bitişik kareden 1'ine girebilir (aynı karede kalamayacağı veya çapraz olarak hareket edemeyeceği varsayılırsa). Vakum Dünyasının yayları çift yönlüdür, çünkü herhangi bir kareye bitişik herhangi bir kareden ulaşılabilir ve durum uzayı bir ağaç değildir, çünkü herhangi bir 4 bitişik kare arasında hareket ederek bir döngüye girmek mümkündür.

Durum uzayları sonsuz veya sonlu ve ayrık veya sürekli olabilir.

Boyut

Belirli bir sistem için durum uzayının boyutu, alanın olası konfigürasyonlarının sayısıdır.^[3]

Sonlu

Durum uzayının boyutu sonlu ise, durum uzayının boyutunun hesaplanması bir kombinatoryal sorun.^[5] Örneğin, Sekiz kraliçe yapboz Durum uzayı, 8 parçayı 8x8 satranç tahtasına yerleştirmenin tüm olası yolları sayılarak hesaplanabilir. Bu, 64'lük bir setten değiştirmeden 8 pozisyon seçmekle aynıdır veya

${ displaystyle { binom {64} {8}} = 4.426.165.368}$

Bu, kraliçelerin yasal konfigürasyonlarının sayısından önemli ölçüde daha fazladır 92. Pek çok oyunda etkili durum alanı, tüm erişilebilir / yasal durumlara kıyasla küçüktür. Bu özellik aynı zamanda Satranç etkin durum uzayı, oyun kurallarına uygun hareketlerle ulaşılabilen konumlar kümesidir. Bu, mevcut satranç taşlarının kombinasyonlarını doğrudan tahtaya yerleştirerek elde edilebilecek konum dizisinden çok daha küçüktür.

Sonsuz

Tüm sürekli durum uzayları, karşılık gelen bir sürekli işlev ve bu nedenle sonsuzdur.^[3] Ayrık durum uzayları da (sayılabilir şekilde ) zamana bağlı "sayaç" sistemin durum uzayı gibi sonsuz boyut,^[2] sisteme benzer kuyruk teorisi {0, 1, 2, 3, ...} durum uzayına sahip bir satırdaki müşteri sayısını tanımlama.

Keşif

Bir durum uzayını keşfetmek, bir hedef durum arayışında olası durumları listeleme sürecidir. Durum uzayı Pacman örneğin, tüm yem peletleri yenildiğinde bir hedef durumu içerir ve Pacman'i tahtada hareket ettirerek keşfedilir.^[6]

Arama Durumları

Bir arama durumu, bir durum uzayındaki bir dünya durumunun sıkıştırılmış bir temsilidir ve keşif için kullanılır. Arama durumları, bir durum uzayının genellikle uzayı keşfetmek için gerekenden daha fazla bilgiyi kodlaması nedeniyle kullanılır. Her bir dünya durumunu yalnızca keşif için gereken bilgilere sıkıştırmak, aramadaki durumların sayısını azaltarak verimliliği artırır.^[6] Örneğin, Pacman uzayındaki bir durum, Pacman'ın baktığı yön (yukarı, aşağı, sola veya sağa) hakkında bilgi içerir. Pacman'de yön değiştirmenin herhangi bir maliyeti olmadığı için, Pacman için arama durumları bu bilgiyi içermeyecek ve arama alanının boyutunu Pacman'ın bakabileceği her yön için 4 kat azaltacaktır.

Yöntemler

Standart arama algoritmaları, ayrık durum uzaylarını keşfetmede etkilidir. Aşağıdaki algoritmalar her ikisini de gösterir tamlık ve bir durum uzayı aramada optimallik.^[6][7]

• Kapsamlı Arama
• Arama
• Tekdüzen Maliyet Araması

Bu yöntemler doğal olarak sürekli durum uzaylarını keşfetmeye kadar uzanmaz. Belirli bir hedef durumu arayışında sürekli bir durum uzayını keşfetmek, keyfi bir durumu optimize etmeye eşdeğerdir. sürekli işlev bu her zaman mümkün değildir, bakın matematiksel optimizasyon.

Ayrıca bakınız

Referanslar