Verilen iki nokta arasında bağlantı olup olmadığını bulmak

[Erdem]

p ve q iki nokta olsun. Tüm noktaların sayısal değerleri veriliyor. Bu noktalar arasında bir bağlantı olup olmadığını nasıl buluruz?

p ve q arasındaki yolu bulmamıza gerek yok. Sadece bağlantılıysa programın bağlı demesi yeterli. Tabi bunu elimize alıp parmaklarımızla yolları takip ederek de çözebilirdik. Ama bu oldukça uzun sürebilir.

Bunu bir baskı devre üzerindeki yollar olarak da düşünebilirsiniz.

[The Gariban]

P noktasının değeri alınır
Pnin x değeri bir artırılır kırmızı renk varmı diye sordurulur yoksa x değeri bir azaltılır kırmızı varmı diye sordurulur yoksa y değeri bir artırılır kırmızı renkmi diye sordulur yoksa y bir azaltılır kırmızı varmı diye sordurulur. Yoksa "Bağlantı yok mesajı" verdirilir(4 yönede bakıldığı için)
Diğer 3 olasılıktan biri(yeni x veya y değerinde kırmızı varsa yeni x ve y değerleri bu değere atanır ve P koordinat değeri ile karşılaştırılır.Eşitse "P ile Q arasında iletim var " mesajı verilir.
Temel olarak bu şekilde yapılabilir diye düşünüyorum
(Yada 45 derecelik açılarda sözkonusu ise ki  8 olasılıkta kontrol edilmesi gerekecek)
Tabiki bu algoritması belki bunu otomatik yapan Visual C  birşeyler olabilir onu bilmiyorum

[Yuunus]

...koordinatları; iki noktayı birleştirirken kaydedebilirsiniz. sonrada kayıtlardan birleşik mi ayrı mı kontrol edebilirsiniz.

[Erdem]

Aslında piksel yöntemini eğer fırsat bulabilirsem grafiksel ortamda deneyeyim. Ama oradaki sorun dallanmanın çok fazla olması. Bir de örneğin 2 nokta değil de bir milyon tane noktanın birbirine bağlı olup olmadığını denetlemek istediğimizi düşünelim. O zaman büyük ihtimalle işlem gücümüz yetersiz kalacaktır.

Soruyu hem daha ayrıntılı anlatayım hem de basitleştireyim.

Örneğin bu numaralar sizin de bahsettiğiniz gibi dijital bir fotoğraftaki pikselller olabilir. Ya da bir ağdaki bilgisayarlar, sosyal ağdaki arkadaşlar, ya da bir bilgisayar yongasındaki transistörler gibi bileşenler olabilir.

İlkönce bu noktaların arasında bir bağ yok.

bağla şeklinde bir komutla iki sayı arasında bir bağ oluşturabilmeliyiz ve bağlıMı işlevi ile de p ile q'nun birbirine bağlı olup olmadığını kontrol edebilmeliyiz.

bağla(4, 3)
bağla(3, 8)
bağla(6, 5)
bağla(9, 4)
bağla(2, 1)
bağlıMı(0, 7) Hayır
bağlıMı(8, 9) Evet
bağla(5, 0)
bağla(7, 2)
bağla(6, 1)
bağla(1, 0)
bağlıMı(0, 7) Evet

Noktaları bağladıktan sonra şu şekilde bir resim oluşuyor. İsterseniz kağıt kalem ile deneyebilirsiniz.



Sonra bu bağlı noktalar da kendi arasında bir küme oluşturuyor.



Programın şöyle çalışması gerekiyor.

* Girişten nesne sayısını N oku (giriş dosyasının en başında kaç tane sayı okuyacağımız yazıyor)

* Tekrarla:

        Girişten bir çift tamsayı oku

        Eğer bağlı değillerse bağla ve bağlı çiftleri ekrana yaz.

Örneğin giriş dosyamız şu şekilde olsun:

10
4 3
3 8
6 5
9 4
2 1
8 9
5 0
7 2
6 1
1 0
6 7

Bu durumda zaten birbirine bağlı olduğu için yeşille gösterilen kısımları yazmıyoruz.

Bunu grafiksel olarak gösterirsek programın çalışması şu şekilde:



Programın en sonunda da birbirine bağlı küme sayısını yazdırıyoruz. Bu durumda 2 olmuş oluyor

Programı da program < giriş.txt şeklinde çalıştırabilmeliyiz.

[rree]

Her cizgi veri tabanında "kordinat dataları" bulundursun. Diyelim  o çizgiyi sileceksin. Verideki dataklerı silecek bir program rahat yazılır. Gelelim sorunuza çizgi iki noktaya bağlımı. Soralım veri tabanına  o kordinatta  veri tabanında veri varmı.Bence hızlı çalışan bir veri tabanını yöntemi bir çok esneklikler getirir.
Diyelim çizgiyi geçici olrak göstermiyeceksin mesela yazıcıdan alırken maskelenecek  o çizgiye ait verileri maskelersin.

[The Gariban]

Aslında piksel yöntemini eğer fırsat bulabilirsem grafiksel ortamda deneyeyim. Ama oradaki sorun dallanmanın çok fazla olması. Bir de örneğin 2 nokta değil de bir milyon tane noktanın birbirine bağlı olup olmadığını denetlemek istediğimizi düşünelim. O zaman büyük ihtimalle işlem gücümüz yetersiz kalacaktır.

Bu bir tane nokta diğer noktaya bir milyon seçecekten biri ile bağlı olma ihtimalimi oluyormuş
Bu nasıl mantık   bir piksele bağlantı için milyon pixellimi kontrol etmek gerekiyormuş

[Erdem]

bir piksele bağlantı için milyon pixellimi kontrol etmek gerekiyormuş

Hayır demek istediğim bu değildi. Sadece 2 noktanın bağlantılı olduğunu değil de 1 milyon noktanın birbirine bağlı olup olmadığını kontrol ettiğimizi düşünelim demek istemiştim.

Evet haklısınız normal dosya yerine veritabanı da kullanılabilir. Ancak bizim sorunumuz programın bu verileri işlemesinde. Bir dosyadan ya da bir veritabanından belki yarım saniye ya da daha kısa süre içerisinde bu bilgileri okuyabiliriz. Ama program içinde bu bilgileri nasıl kullanacağız. Nasıl bir veri yapısı kullanmamız lazım?

10
4 3
3 8
6 5
9 4

Örneğin giriş dosyasında bu bilgiler var aslında. 10 tane sayı okunacak. 4 ile 3 birbirine bağlı, 3 ile 8 birbirine bağlı vs.. programa sürekli veri geliyor. Programın bu bilgileri işleyip yukarıdaki gibi bir çıktı vermesi için nasıl bir veri yapısı kullanmamız lazım?

Koordinatlar konusunda söylediklerinize katılıyorum örneğin 0 noktasının koordinatları (0, 0) ve 1 noktasının koordinatları (10, 0) olabilir. Ama diğer arkadaşların kafasını karıştırmamak için koordinatlara girmiyorum. Zaten iki noktanın birbirine bağlı olup olmadığını öğrendikten sonra koordinatları istediğimiz gibi kullanabiliriz.

[rree]

Bu konuda araştırma yapmış değilim ama beyin jimlastiği şeklinde yorumum.

Veri tabanındaki mantık  Çizgi00001{kor1,2- kor2,4-kor4-8-...........Korxn,yn}

Ekrana tüm cizgiler kordinat kümeleri ile çizilsin
Ekran çizgileri çizdirilir iken ram bellekte bir katman layer eklensin. ekrana temsil layer
Bu ikinci katman sadece ram bellekte. İkinci katmana her kordinat hangi cizgiye ait bilgiler atansın.

Sonra diyelim ekrana çizilmiş bir çizginin fare imleci üzerine geldi diyelim. çizgiye aait en yakın grid
kordinatını bulsun.  Diyelim kordinat 2,4
Sonra ikincileyer deki 2,4 adresli datayı okusun
yukarıdaki örnekte 00001  birinci çizgi olduğu öğrenilir.

Hangi çizgi olduğu öğrenildiğine göre  veri tabanındaki kordinatlar taranır istenilen grid nokta kordinatı varmı bakılır.
Not: çizgiler grid adımları şeklinde 25 th 50th gibi kavramlar ile yapılmalı yoksa serbest çizim şeklinde olursa  buna ne işlemci gücü yeter nede veri tabanı.

[Erdem]

Aslında şu an çizimle ilgilenmiyoruz. Veritabanı olarak da basit metin dosyaları kullanıyoruz.

giriş.txt dosyamız şu şekilde:

10
4 3
3 8
6 5
9 4
2 1
8 9
5 0
7 2
6 1
1 0
6 7

Programın şöyle çalışması gerekiyor.

* Girişten nesne sayısını N oku (giriş dosyasının en başında kaç tane sayı okuyacağımız yazıyor)

* Tekrarla:

        Girişten bir çift tamsayı oku

        Eğer bağlı değillerse bağla ve bağlı çiftleri ekrana yaz.


Programı program < giriş.txt şeklinde çalıştırdığımız zaman

4 3
3 8
6 5
9 4
2 1
5 0
7 2
6 1
2 bileşen

çıktısını vermeli. Böyle bir programı C, C++, D, Python ya da Java ile yazınız 
mesaj birleştirme:: 20 Eylül 2012, 00:28:59

0 1 2 3 4 5 6 7 8 9
---------------------
|0|1|2|3|4|5|6|7|8|9| ilk durum
---------------------

---------------------
|0|1|2|3|3|5|6|7|8|9| bağla(4, 3)
---------------------

---------------------
|0|1|2|8|8|5|6|7|8|9| bağla(3,
---------------------

---------------------
|0|1|2|8|8|5|5|7|8|9| bağla(6, 5)
---------------------

Bu problemin çözüm yollarından bir tanesi basitçe bir dizi kullanmak. İlk durumda bu 10 tane nesnemizin hiç biri birbirine bağlı değil. Sadece kendilerine bağlı. O yüzden 0. sırada bulunan eleman 0'a bağlı anlamında 0 .. 9 arası değerler veriyoruz. Sonra 4'ü 3'e bağla dediğimizde ilk eleman ikincinin değerini alıyor. 3'ü 8'e bağla dediğimizde ise 3.sırada bulunan elemana karşılık gelen tüm değerler bu durumda 3'lerin hepsini 8 yapıyoruz.  Bu durumda 3,4 ve 8'in birbirine bağlı olduğu diziye bakarak görülebiliyordur sanırım.

Programın kaynak kodunu yazmadım. Ama merak eden arkadaşlar D ile yazılmış kaynak kodunu bu sayfadan inceleyebilirler.

https://github.com/erdemoncel/algoritmalar

Denemek için Digitalmars'ın DMD derleyicini indirip programı derledikten sonra

bbhizlibagla < bbKucuk.txt

şeklinde deneyebilirsiniz. Örneğin bbBuyuk.txt dosyasında 2 milyon satır var

Bir de bu program aslında büyük miktarda verilerle yavaş çalışıyor. Sanırım veri miktarı milyarlarcaya çıkınca 30 sene kadar sürüyormuş. İşin ilginç tarafı sadece farklı bir algoritma kullanarak aynı verinin dakikalar, saniyeler içinde işlenebilmesi.

Hızlı çalışan yöntem ise dengeli ağaç yapısını kullanıyor. Merak eden arkadaşlar olursa izah edebilirim.

Bir de bunun uygulamaları çok ilginç. Örneğin arkadaşların bahsettiği grafiksel hale çevirmeyi bir kaç basit adımla yapabiliyoruz.



Beyazlara dikkat.