8
votes

Compte tenu d'un ensemble de conditions, détermine algorithmique, un seul peut être vrai

Étant donné un ensemble de deux conditions logiques ou plus, est-il possible de déterminer algorithmiquement que l'un d'entre eux évaluera exactement à vrai? Par exemple:

# this should pass, since for every X, only one condition is taken
cond 1: (X >= 1.0) 
cond 2: (X < 1.0)

# this should fail
cond 1: (X < 1.0)
cond 2: (X > 2.0)

# this should also fail, since X=1.0 would meet both conditions
cond 1: (X < 2.0)
cond 2: (X > 0.0)

# there may be more than one variable involved
cond 1: (X >= 1.0 && Y >= 0)
cond 2: (X < 1.0 && Y <= -1)

x> = y && li>
x.within_radius (0.4) code> li>
x dans certains_array code> li>
x * y li> ul> Mise à jour finale h3> Cela semble être une solution qui couvre toutes les conditions possibles n'est pas possible (ou du moins, compte tenu de mes connaissances limitées, non possibles dans le délai imparti pour le problème) . Va reviser cela un jour, mais pour désormais accepter la réponse qui m'a apporté en avant le plus éloigné. P> P>

algorithm validation conditional-statements language-agnostic logic

10 commentaires

Les nulls sont-ils possibles? Ce qui suit peut être un bon point de départ: en.wikipedia.org/wiki/formal_versification

Le dernier devrait échouer aussi ne devrait-il pas cela? Si x = 0 et y = 0, les deux conditions sont fausses.

@Chris: Tu as raison. Merci. Mettra à jour.

@LUCERO: (sauf si j'ai mal compris votre question) Les NULLS ne sont pas des résultats possibles de chaque état. Chaque condition devrait évaluer à vrai de faux.

Étant donné que les décisions font partie d'un arbre de décision, vous n'avez-vous pas à inclure également les conditions des parents? Par exemple, lorsque vous descendez un chemin où x> 2 , alors deux conditions suivantes x <1 et x> 0 font Pas Clash, mais votre outil de vérification statique signalerait probablement qu'ils le font.


                                        
                                                                            @heinrich Désolé, mauvaise utilisation de la terminologie de ma part. Ce n'est pas tout à fait un arbre de décision dans le sens pur, mais un point de l'exécution du code où les conditions déterminent ce qu'on appelle ensuite
                                        
                                                                            Oui; Ce que je veux dire, c'est que une condition pourrait devenir superflue car elle est uniquement vérifiée lorsque le code précédent l'a déjà dirigé. Par exemple:  si (x> 2) {si (x <1) {... cette branche est superflue! } else {...}} else {...} 

                                        
                                                                            @LSC, supposons que vous appliquez cela à un code SQL. Les variables  x  et  y  peuvent être nuls dans ce cas. Donc, pour le premier échantillon, si  x = null  est une des deux conditions étant vraies?

                                        
                                                                            @LUCERO, Aussi loin que je sache, il n'est pas possible que les variables soient nulles. Avec certaines des variables étant des valeurs calculées, je suppose qu'il leur est possible d'être INF / -Inf / Nan, mais dans le cas de la NAAN, toute la simulation est considérée comme erronée de toute façon, donc j'étais réduisant cela.
                                        
                                                                            @heinrich, dans l'application actuelle, chaque condition est évaluée indépendamment et son résultat n'est influencé par aucune autre condition.

4 Réponses : 0 votes sont les blocs de construction de vos conditions juste une variable entière, Un opérateur de comparaison sur (<, <=,>,> =), chiffres (supposons des entiers)? et les conditions finales sont construites à partir de ceux-ci utilisant && et ||? Peut-on supposer que toutes les variables entières sont indépendantes? Dans ces conditions, je suppose que cela peut être vérifié algorithmique. Je mettrais toutes les gammes valides par variable dans une structure de données et vérifier les intersections. Edit: Comme cela ne semble pas être le cas, la meilleure solution serait probablement de regrouper les différents types de conditions afin que les conditions de chaque groupe puissent être évaluées statiquement les unes contre les autres. Le type de conditions supposées par moi de votre première description serait l'un de ces groupes. 1 commentaires (Modifier) J'ai bien peur que les variables ne se limitent pas à des chiffres et peuvent contenir des constructions similaires à la fonction qui renvoient true / false (par exemple X.WithIn_radius (0.3) ou (x en somard)). Les conditions ne se fusionnent pas dans une condition finale, mais plutôt, chaque condition est indépendante de l'autre et est attribuée par les utilisateurs à une série de chemins pour déterminer la voie de la simulation (d'où la nécessité de validation). 3 votes Edit: Je vais reformuler parce que cela semble être que les autres réponses supposent un tas de choses qui ont depuis été confirmées: Si vous pouvez indiquer vos conditions (et la contrainte que celle qui est vraie) en termes de Arithmétique Presburger , vous pouvez alors écrire une procédure de décision pour vérifier que les biens de manière statique. Cela semble parfaitement réalisable des exemples ci-dessus. L'approche "Instrument émoussé" consiste à interface essentiellement à quelque chose comme un prouveur de théorème automatique ou un solveur SMT (où vous essayez essentiellement de prouver la négation de la déclaration "Il existe une valeur X qui satisfait à la contrainte1 XOR Contraint2" ). J'ai une interface programmatique avec CVC3 avant, et l'a trouvé très bon de travailler avec , mais ma compréhension est que cela a été dépassé par d'autres solveurs SMT. Quelque chose d'autre que vous faites pour résoudre ce problème va probablement finir par approximation de la mise en œuvre du type d'outils que j'ai suggéré, je pense. Selon exactement comment vos contraintes sont spécifiées, vous pourrez peut-être vous éloigner de la mise en œuvre d'une sorte de procédure de décision pour quelque chose comme Arithmétique Presburger . 2 commentaires Merci Gian. Je vais avoir une lecture et voir cela correspondrait à la facture. D'accord avec Gian. Vérifiez également le concept de «contrat de code», par exemple dans Eiffel. Un bon travail sur la vérification statique des contrats de code ici: recherche.microsoft.com/fr- US / Projets / Contrats , ici: PEXForFun.com/... Et ici: canal9.msdn.com / Posts / Peli / ... 1 votes En général, non. Mais si vous demandez vraiment que ce que vous demandez vraiment, c'est que cela soit possible conformément aux conditions de combinaisons logiques booléennes d'inégalités sur un ensemble fini de variables entières indépendantes avec des constantes, alors il y a de l'espoir. Vous pouvez vérifier de manière exhaustive en permutant les variables avec les constantes qui apparaissent dans vos inégalités (et +1 et -1 de ces constantes) et vérifiez que le nombre de conditions qui détiennent sont toujours 1. 1 commentaires C'était ce que je pensais, mais j'espérais que le cerveau collectif de S.O. peut me montrer sinon. Merci. 1 votes Si vous souhaitez trouver si une seule condition est vraie (sur deux ou plus de conditions possibles), il peut être utile de faire référence à cette question XOR sur SO: Xor-of-Three-valeurs . Prise directement de sa réponse: xxx dans votre cas: xxx Il y a aussi une solution générale où vous incrémentez un compte à chaque condition est vrai, puis vérifiez le nombre de comptes sur 1 une fois que toutes les conditions ont été testées. 2 commentaires Merci Gary. J'ai déjà une solution en place qui fait à peu près ça. Ce que je me demande maintenant, c'est s'il est possible de le vérifier statiquement et non au moment de l'exécution. Les valeurs d'A, B, C ne sont pas connues à l'avance. Ok, je n'ai pas compris la question au début. Bonne chance.

Articles qui pourrait vous intéresser : Calculer la différence dans l'échelle d'évaluation alphabétique Complexité de Trouver tous les multiples de 3 et 5 entre 1 et 10 000 000 Ma vérification pour savoir si un graphique est un arbre binaire renvoie toujours faux Comment trouver le nombre d'itérations de l'algorithme de recherche binaire?

Compte tenu d'un ensemble de conditions, détermine algorithmique, un seul peut être vrai

Mise à jour finale h3>