Birden fazla vektörden tanımlanmamış elemanlar nasıl bulunur? bir vektör içinde farklı olan birden fazla tam sayı numaralarını içeren, her biri

Question

Verilen pek çok vektör/setleri,. Şimdi kontrol etmek istiyorum, tek bir elemanının elemanından her bir vektörü/kümesi verilen bir setin var olup olmadığını kontrol etmek istiyorum, aynı zamanda çıkarılan numaralar birbirinden nonidentical'dur. Verilen örnek için

, a, b, c, d olarak ayarlar:

a <- (1,3,5); 
b <- (3,6,8); 
c <- (2,3,4); 
d <- (2,4,6) 

Gibi setleri edinmek (1, 8, 4, 6) ya da (3, 6, 2, 4) ..... aslında, sadece varlığı kanıtlamak için böyle bir set bulmam gerekiyor. vahşi kuvvet arama uygulanması

m verilen setleri boyutu kontrol etmek için, maksimal m^K kombinasyonları olabilir, k verilen setleri sayısıdır. Herhangi zeki yolları

var mı? Teşekkür ederiz!

Answer 1

Bir ikili grafikte bir eşleme olarak sorununuzu yeniden formüle edilebilir:

• sol tarafının düğüm kümesi varken
• sağ tarafının düğüm kümeleri görünen tamsayı vardır.

Belirtilen tam sayıyı içeriyorsa, bir "set" düğümü ve bir "tamsayı" düğümü arasında bir kenar vardır. Ardından, bu ikili grafikte eşleşen bir bulmaya çalışıyor: Her set bir tamsayıya ilişkilendirilir ve hiçbir tamsayı iki kez kullanılacaktır. Böyle bir eşleşmeyi bulmak için basit bir algoritmanın çalışma süresi O (| V || E |), burada | V | (m + 1) k ve | E | 'den küçüktür mk'ye eşittir. Yani O (m^2 k^2) bir çözüm var. Bakınız: Matching in bipartite graphs. ikili eşleştirme için

Algoritma:

algoritması odaklı grafikler üzerinde çalışır. Başlangıçta, tüm kenarlar soldan sağa doğru yönlendirilmiştir. Aralarındaki kenar sağdan sola doğru yönlendirilirse iki düğüm eşleştirilir, böylece başlangıçta eşleşme boş olur. Algoritmanın amacı "artırım yolları" (veya dönüşümlü yollar), yani eşleştirmenin boyutunu artıran yollar bulmaktır.

Arttırıcı yol, eşlenmemiş bir sol düğümden başlayan ve benzersiz bir sağ düğüme son veren yönlendirilmiş grafikteki bir yoldur. Bir artırım yoluna sahip olduğunuzda, yoldaki tüm kenarları eşleştirmenin boyutunu artıracak şekilde çevirmeniz yeterlidir. (Eşleşmenin boyutu, eşleşmeye ait olmayan bir daha fazla kenara sahip olduğunuz için artacaktır. Buna, yolun eşleşen, soldan sağa ve kenarlara eşleşmeyen kenarlar arasında geçiş yapması nedeniyle bir dönüşümlü yol adı verilir. sağdan sola)

İşte

Eğer bir takviye yolu bulmak nasıl:.,

1. tüm düğümler ziyaret edilmemiş olarak işaretlenmiş
bir ziyaret edilmemiş ve eşsiz sol düğümü almak
2. ,
3. bir do Eşsiz bir doğru düğümü bulana kadar ilk önce derinliği araştırın (sonra bir yükseltme yoluna sahipsiniz). Eşsiz bir doğru düğüm bulamıyorsanız, 2'ye gidersiniz.

Arttırma yolu bulamıyorsanız, eşleşme en uygunudur.

Bir artırım yolunun bulunması karmaşıklık O (| E |) olup, bunu en çok min (k, m) sürelerle yaparsınız, çünkü en iyi eşleşmenin boyutu k ve m tarafından sınırlandırılmıştır. Böylece probleminiz için karmaşıklık O olacaktır (mk min (m, k)).

Ayrıca, kanıtlarla ilgili daha kapsamlı bir açıklama için this reference, bölüm 1'i de görebilirsiniz.