İçeriğe geç
NEBİLİM AĞI ÇEVRİMİÇİ22.11.2026 · BİLİM, EVREN & TEKNOLOJİ
NeBilim.net

Her cevap,
yeni bir soru açar.

OBSERVATION / 638

Üç Yöntem, Tek Sorun: Klasik ve Yapay Zeka Yaklaşımlarıyla “Hiçbir Üçlü Bir Düzgün Hattı Oluşturmaz” Problemi

Yayın:

Hiçbir Üç Noktanın Doğrusal Olmaması problemi, n × n boyutunda bir ızgara üzerine hiçbir üç noktanın aynı doğru üzerinde gelmeyeceği şekilde…

Üç Yöntem, Tek Sorun: Klasik ve Yapay Zeka Yaklaşımlarıyla “Hiçbir Üçlü Bir Düzgün Hattı Oluşturmaz” Problemi

Özet

Arka Plan:

Hiçbir Üç Noktanın Doğrusal Olmaması problemi, n × n boyutunda bir ızgara üzerine hiçbir üç noktanın aynı doğru üzerinde gelmeyeceği şekilde yerleştirilebilecek maksimum nokta sayısını sorgular ve kombinatoryal geometrideki ünlü bir problemi temsil eder.

Yöntemler:

NeBilim sitesini Google’da tercih edilen kaynak olarak seç

Üç yaklaşımı karşılaştırıyoruz: (i) Gurobi kullanılarak uygulanan tamsayı doğrusal programlama (ILP), (ii) PatternBoost aracılığıyla transformer tabanlı örüntü öğrenimi ve (iii) yakınsak politika optimizasyonu (PPO) kullanılarak uygulanan pekiştirmeli öğrenme.

Sonuçlar:

ILP, 19 × 19 ızgaralara kadar kanıtlanabilir şekilde optimal çözümler elde eder. PatternBoost, 14 × 14 ızgaralara kadar optimal performansa ulaşır ve 15 × 15 ızgaralarda 29 nokta bulur (optimal değer 30’dır). PPO, 10 × 10 ızgaralarda mükemmel çözümler elde ederken, kısıt ihlalleri nedeniyle 11 × 11 ızgaralarda başarısız olur. Dört sabit zaman sınırı denemesi boyunca ILP n = 17’ye kadar güvenilirken, PatternBoost n = 12’ye kadar başarılı olmuş ve PPO yalnızca n = 10’da bir kez başarılı olmuştur.

Sonuçlar:

Klasik optimizasyon, kesin çözümler için temel olmaya devam ederken, yapay zeka yöntemleri daha küçük örneklerde rekabetçi performans sunar. Çözücüler ile öğrenilmiş sezgileri birleştiren hibrit yaklaşımlar, daha büyük ızgaralara ölçekleme için en umut verici seçenek gibi görünmektedir.

1 Giriş

Hiçbir Üç Noktanın Doğrusal Olmaması problemini ele alıyoruz: Bir n × n ızgara üzerine hiçbir üç noktanın aynı doğru üzerinde gelmeyeceği şekilde yerleştirilebilecek maksimum nokta sayısı nedir? Şekil 1, 10 × 10’luk bir ızgara için optimal bir çözümü göstermekte ve hiçbir üç noktanın doğrusal olmamasıyla maksimum 20 noktaya ulaşmaktadır.

Güvercin yuvası ilkesinden kaynaklanan 2n noktalık basit bir üst sınır mevcuttur, çünkü hiçbir satır veya sütun iki’den fazla nokta içeremez. İlk basit olmayan alt sınır, Roth tarafından modüler parabol yapıları kullanılarak yaklaşık n nokta yerleştirilerek oluşturulmuştur . Bu sınır, Hall, Jackson, Sudbery ve Wild tarafından modüler hiperbol yapıları kullanılarak yaklaşık 1.5n‘e yükseltilmiş ve bu değer hâlâ kanıtlanmış en iyi alt sınırdır . n ≤ 60 için 2n noktaya ulaşan kesin çözümler bulunmuştur (T. Prellberg, özel iletişim, 2026). Ancak Guy ve Kelly, yeterince büyük n değerleri için maksimum değerin asimptotik olarak yalnızca cn noktaya yaklaştığını varsaymışlardır; burada c = (2π2/3)1/3≈1.874’tür (); bu değer daha sonra c=π/√≈.c=π/3≈1.814 olarak düzeltilmiştir (). Bu durum, kanıtlanmış en iyi sonuç ile varsayılan sınır arasında önemli bir boşluk bırakarak problemin devam eden zorluğunu vurgulamaktadır.

İçsel kombinatoryal ilgisinin ötesinde, hiçbir üç noktanın doğrusal olmaması kısıtı, modern enerji sistemlerinin iletişim katmanlarında (örneğin akıllı şebekeler ve dağıtılmış algılama/etkinleştirme) düğüm yerleşimi için soyut bir model olarak da görülebilir. Yönlendiriciler veya röle düğümleri koridorlar, besleme hatları veya trafo merkezleri boyunca yaklaşık olarak dikdörtgensel düzenlerde yerleştirildiğinde, doğrusal üçliler istenmeyen olabilir: basit girişim ve paylaşılan kanal (çarpışma) modellerinde, bir çizgi üzerindeki ara düğüm baskın bir girişimci (veya kaçınılmaz bir röle) olarak hareket ederek o yöndeki güvenilir iletişimi bozabilir. Bu nedenle, “hiçbir üç noktanın doğrusal olmaması” kuralını uygulamak, bir ağda mekansal çeşitliliği teşvik etmek ve doğrudan görüş hizalanması etkilerini azaltmak için doğal bir yoldur; bu da enerji sistemleri için iletişim altyapısı planlamasında kullanılan tasarım sezgilerine temiz ve ayrık bir alternatif sunar. Bu bakış açısı aynı zamanda Birleşik Krallık Araştırma ve İnovasyon (UKRI) tarafından desteklenen, gelecekteki enerji sistemleri için dayanıklı iletişim altyapıları üzerine daha geniş, uygulama odaklı çalışmalarla da uyumludur. Genel olarak, bu makalede incelenen hiçbir üç noktanın doğrusal olmaması problemi, iletişim kuran cihazın kendisinin iletişim yolunu engellediği her türlü iletişim ağına uygulanabilir. Örneğin, belirli bir ızgara üzerindeki diğer tüm cihazlara ışık ışınları göndererek iletişim kuran, ancak yolda olmaları durumunda ışık iletimini engelleyen optik cihazlar düşünülebilir. Sınırlı bir alanda bu tür cihazların sayısını maksimize etme ve onları ayrık bir ızgara üzerine en verimli şekilde iletişim kurabilecekleri şekilde yerleştirme problemi, bu makalede incelenen matematiksel problemin aynısıdır.

Özyinelemeli geri izleme algoritmaları ve tamsayı doğrusal programlama (ILP) gibi geleneksel hesaplama yaklaşımları, hiçbir üç noktanın doğrusal olmaması problemini, doğrusallık kısıtlarını cebirsel olarak kodlayıp dallanma ve sınırlama optimizasyonu kullanarak bir kısıt tatmin görevi olarak çerçeveler (; ). Flammenkamp’ın ilk hesaplama çabaları, gelişmiş budama teknikleriyle kapsamlı geri izleme araması kullanarak n = 52’ye kadar optimal konfigürasyonları başarıyla belirlemiştir (). Bu sayma yöntemleri, simetrik eşdeğerleri ve kısıtları ihlal eden konfigürasyonları elerken arama uzayını sistematik olarak keşfeder, ancak ızgara boyutu arttıkça hesaplama süresi de üstel olarak artar. Bu klasik yöntemler iki temel ölçekleme zorluğuyla karşı karşıyadır. Birincisi, arama uzayı 2n2 şeklinde üstel olarak büyür, bu da kapsamlı aramayı daha büyük n değerleri için imkansız kılar. İkincisi, yerleştirilen her yeni noktayla kontrol edilmesi gereken doğrusallık kısıtlarının sayısı kuadratik olarak artar, bu da her yeni noktanın yerleştirilmesini giderek daha maliyetli hale getirir.

Temel Bulgular ve Genel Değerlendirme

RothK. F. (1951). On a problem of Heilbronn. J. London Math. Soc. s1-26, 198–204. doi: 10.1112/jlms/s1-26.3.198

SchuetzM. J. A.BrubakerJ. K.KatzgraberH. G. (2022). Combinatorial optimization with physics-inspired graph neural networks. Nat. Mach. Intell. 4, 367–377. doi: 10.1038/s42256-022-00468-6

SchulmanJ.MoritzP.LevineS.JordanM.AbbeelP. (2016). “High-dimensional continuous control using generalized advantage estimation,” in Proceedings of International Conference on Learning Representations (Appleton, WI: ICLR).

SchulmanJ.WolskiF.DhariwalP.RadfordA.KlimovO. (2017). Proximal policy optimization algorithms. arXiv [preprint]. arXiv:1707.06347.

TowersM.KwiatkowskiA.TerryJ.BalisJ. U.De ColaG.DeleuT.et al. (2024). Gymnasium: a standard interface for reinforcement learning environments. arXiv [preprint]. arXiv:2407.17032.

TsuchiyaY.TakefujiY. (1995). A neural network algorithm for the no-three-in-line problem. Neurocomputing8, 43–49. doi: 10.1016/0925-2312(94)00003-4

VaswaniA.ShazeerN.ParmarN.UszkoreitJ.JonesL.GomezA. N.et al. (2017). “Attention is all you need,” in Proceedings of Advances in Neural Information Processing Systems (La Jolla, CA: NeurIPS), 5998–6008.

Özet

Anahtar Kelimeler

kombinatoryal optimizasyon, kısıt tatmini, tamsayı doğrusal programlama, hiçbir üç noktanın doğrusal olmaması, PatternBoost, pekiştirmeli öğrenme, transformer modelleri

Atıf

Ramanathan P, Prellberg T, Lewis MJ, Beck C, Joshi PD, Dandekar RA, Dandekar R and Panat S (2026) Three methods, one problem: classical and AI approaches to no-three-in-line. Front. Artif. Intell. 9:1799444. doi: 10.3389/frai.2026.1799444

Alındı

29 Ocak 2026

Revize edildi

05 Ağustos 2026

Kabul edildi

05 Ekim 2026

Yayınlandı

17 Kasım 2026

9 – 2026

Rashid Ibrahim Mehmood, İslam Medine Üniversitesi, Suudi Arabistan

Jinran Wu, Queensland Üniversitesi, Avustralya

Marco Gavanelli, Ferrara Üniversitesi, İtalya

© 2026 Ramanathan, Prellberg, Lewis, Beck, Joshi, Dandekar, Dandekar ve Panat.

Bu, Creative Commons Atıf Lisansı (CC BY) şartları altında dağıtılan açık erişimli bir makaledir. Orijinal yazarların ve telif hakkı sahiplerinin belirtilmesi ve bu dergideki orijinal yayına kabul edilen akademik uygulamalara uygun olarak atıfta bulunulması koşuluyla, diğer platformlarda kullanımı, dağıtımı veya çoğaltılması mümkündür. Bu şartlara uymayan hiçbir kullanım, dağıtım veya çoğaltma iznli değildir.

*İletişim: Thomas Prellberg, t.prellberg@qmul.ac.uk.

Bu makalede ifade edilen tüm iddialar yalnızca yazarlara aittir ve yazarların bağlı olduğu kurumların, yayıncının, editörlerin veya hakemlerin görüşlerini yansıtmak zorunda değildir. Bu makalede değerlendirilebilecek herhangi bir ürün veya üreticisi tarafından yapılabilecek iddialar yayıncı tarafından garanti edilmez veya onaylanmaz.

Frontiers | Three methods, one problem: classical and AI approaches to no-three-in-line
Frontiers | Three methods, one problem: classical and AI approaches to no-three-in-line
Kaynak: Frontiersin ↗
💬 Topluluk Masası & Tartışma

Bu gelişme hakkında düşüncelerinizi, donanım deneyimlerinizi veya sorularınızı Topluluk Forumumuzda paylaşın.

Foruma Katıl & Yanıtla ➔
Forumda sor / tartış
AÇIK LABORATUVAR / TARTIŞMA

1 yorum

Fikrinizi bir kaynak, soru veya yapıcı karşı görüşle geliştirin.

Tartışmaya katıl

E-posta adresiniz yayımlanmaz. Zorunlu alanlar * ile işaretlidir.

SEARCH / 001

En az 3 karakter yazın.

ATLAS / NAVIGATION

Bilgi alanları

Ağ Bağlantıları:Robot Süpürge • Uzay & Astronomi • Bilim Haberleri • Tarih • Donanım Forumu
\n\n